#include <cstdio> #include <iostream> using namespace std; const int maxn=1005; int f1[maxn],g1[maxn]; int g(int n); int f(int n){ if(n==1) return f1[n]=8; return f1[n]=(f(n-1)*9%12345+g(n-1)%12345)%12345; } int g(int n){ if(n==1) return g1[n]=1; return g1[n]=(g(n-1)*9%12345+f(n-1)%12345)%12345; } int main(){ int n;cin>>n; cout<<f(n); return 0; }