文件目录

#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;
}