#include <bits/stdc++.h>

using namespace std;

#define  ll long long

int main() {
    //输入+输出重定向
    freopen("../1277.txt", "r", stdin);

    int n;
    cin >> n;
    long long a, b;
    //1位数，0-9
    //2位数，10-99
    //3位数, 100-999
    //n位数  pow(10,n-1)  ---> pow(10,n)-1

    n == 1 ? a = 0 : a = (ll) (pow(10, n - 1));
    b = (ll) (pow(10, n) - 1);

    int count = 0;
    for (ll i = a; i <= b; i++) {
        //数位分离
        ll temp = i;
        int c = 0;
        while (temp) {
            ll ct = temp % 10;
            if (ct == 3) c++;
            temp /= 10;
        }
        if (c % 2 == 0) {
            count++;
            count %= 12345;
        }
    }
    cout << count << endl;

    //关闭文件
    fclose(stdin);
    return 0;
}