AC

#include <iostream>

using namespace std;

const int mod = 12345; const int MAXN = 1005;

long long f[MAXN], g[MAXN];

int main() {

int n;
cin >> n;
f[0] = 1;
g[0] = 0;
for (int i = 1; i < n; i++) {
    f[i] = (9 * f[i-1] + g[i-1]) % mod;
    g[i] = (9 * g[i-1] + f[i-1]) % mod;
}
long long ans = (8 * f[n-1] + g[n-1]) % mod;
cout << ans << endl;
return 0;

}