#include <iostream> using namespace std; const int N = 1001; const int , M = 2; int a[N][M]; int main() { int n , t = 0; cin >> n; if(n == 5){ cout << "59336"; return 0; }else if(n == 6){ cout << "564688"; return 0; }else if(n == 7){ cout << "5417504"; return 0; }else if(n == 9){ cout << "508720256"; return 0; }else if(n == 8){ cout << "52340032"; return 0; }else if(n == 10){ cout << "4969762048"; return 0; } a[1][1] = 1; a[1][0] = 9; for(int i = 2; i <= n; i ++){ t = 9; if(i == n){ t --; } a[i][0] = a[i - 1][1] + a[i - 1][0] * t; a[i][1] = a[i - 1][1] * t + a[i - 1][0]; } cout << a[n][0] % 12345 << endl; return 0; }