#include<bits/stdc++.h>
using namespace std;
int shu[20004]={1,8,73},shu2[20004]={0,9,90};
int main()
{

    int a,b;
    cin>>a;
    for(int i=3;i<=20000;i++)
    {
        shu2[i]=(shu2[i-1]*10)%12345;
    }
    for(int i=3;i<=a;i++)
    {
        shu[i]=(shu[i-1]*9+shu2[i-1]-shu[i-1])%12345;//i位数中3为偶数的数的个数=i-1位数中3为偶数的数的个数*9+i-1位数中3为奇数的数的个数*1
    }
    cout<<shu[a];
    return 0;

}