#include <bits/stdc++.h>

using namespace std;
// NOI 我就想问一声，这是在赛场临时能想出来的办法吗?
// https://www.cnblogs.com/bajdcc/p/8972992.html

#define M 12345

int dp_oushu[10001] = {0};
int dp_jishu[10001] = {0};

int main() {
    //输入+输出重定向
    freopen("../1277.txt", "r", stdin);
    //1位数时，是可以用眼睛看出来结果的，做为动态规划的出发点数据
    dp_oushu[1] = 8;
    dp_jishu[1] = 1;
    int n;
    cin >> n;
    //迭代增加，在上一个数据的基础上进行增加尝试,找出与上一个的关系
    for (int i = 2; i <= n; i++) {
        dp_oushu[i] = (9 * dp_oushu[i - 1] + dp_jishu[i - 1]) % M;
        dp_jishu[i] = (9 * dp_jishu[i - 1] + dp_oushu[i - 1]) % M;
    }
    cout << dp_oushu[n] % M << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}