#include<bits/stdc++.h>
using namespace std;
int shu[20004]={1,8,73},shu2[20004]={0,9,90};
int main()
{

    int a,b;
    cin>>a;
    for(int i=3;i<=20000;i++)
    {
        shu2[i]=(shu2[i-1]*10)%12345;
    }
    for(int i=3;i<=a;i++)
    {
        shu[i]=(shu[i-1]*9+shu2[i-1]-shu[i-1])%12345;//i位数中3为偶数的数的个数=i-1位数中3为偶数的数的个数*9+i-1位数中3为奇数的数的个数*1
    }
    cout<<shu[a];
    return 0;

}

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