#include <bits/stdc++.h>
using namespace std;
long long a[1005] = {0, 9}, b[1005] = {0, 1}; // 偶数个3,奇数个3
int m = 12345, n;
int main()
{
cin >> n;
int k = 9;
for (int i = 2; i <= n; i++)
{
if (i == n)
k = 8;
a[i] = (a[i - 1] * k + b[i - 1]) % m;
b[i] = (b[i - 1] * k + a[i - 1]) % m;
}
cout << a[n];
return 0;
}