1 #include <cstdio>
 2 int N;
 3 int dp[1010][2];
 4 int main(){
 5     scanf("%d",&N); dp[1][1]=1; dp[1][0]=9;
 6     for(int i=2;i<=N;++i){
 7         int k=i==N?8:9;
 8         dp[i][0]=dp[i-1][0]%12345*k+dp[i-1][1]%12345;
 9         dp[i][1]=dp[i-1][1]%12345*k+dp[i-1][0]%12345;
10     }
11     printf("%d",dp[N][0]%12345);
12     return 0;
13 }