1 #include<cstdio>
 2 #include<cstdlib>
 3 #define N 1010
 4 #define mod 12345
 5 
 6 int f[2][2];
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     if (n==1) {printf("9\n");return 0;}
12     f[1][0]=8,f[1][1]=1;
13     int k=0;
14     for (int i=2;i<=n;i++)
15     {
16       f[k][0]=(f[1-k][0]*9+f[1-k][1])%mod;
17       f[k][1]=(f[1-k][1]*9+f[1-k][0])%mod;
18       k=1-k;
19     }
20     printf("%d\n",f[1-k][0]);
21     return 0;
22 }