#include <bits/stdc++.h>
using namespace std;
int odd[20005];  // odd[i]:i位数，有多少个数有奇数个3
int even[20005]; // even[i]:i位数，有多少个数有偶数个3
int main()
{
    int n;
    cin >> n;
    odd[1] = 1;  // 3
    even[1] = 9; // 0 1 2 4 5 6 7 8 9
    for (int i = 2; i <= n; i++)
    {
        if (i == n)
        {
            // 最高位不能是0
            // 3x、1x/2x/4x/5x/6x/7x/8x/9x
            odd[i] = (even[i - 1] + odd[i - 1] * 8) % 12345;
            even[i] = (odd[i - 1] + even[i - 1] * 8) % 12345;
        }
        else
        {
            // 3x、0x/1x/2x/4x/5x/6x/7x/8x/9x
            odd[i] = (even[i - 1] + odd[i - 1] * 9) % 12345;
            even[i] = (odd[i - 1] + even[i - 1] * 9) % 12345;
        }
    }
    cout << even[n];
    return 0;
}