#undef _GLIBCXX_DEBUG
#pragma GCC optimize("Ofast,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <stdio.h>
#include <stdint.h>

int main()
{
    int N;
#pragma warning(suppress : 4996)
    scanf("%d\n", &N);

    if (N > 0) {
        int_fast32_t a = 2, b = 4, c = 10, d = 24, e = 56, f = 132;
        const int_fast32_t x = 2, z = 202101080000, m = 20210108;

        N -= 6;

        while (N > 0)
        {
            a = x * (f + d);
            b = x * (a + e);
            c = x * (b + f);
            d = x * (c + a);
            e = x * (d + b);
            f = x * (e + c);

            if (f >= z) {
                d -= z;
                e -= z;
                f -= z;
            }

            N -= 6;
        }


        switch (N % 6) {
        case 0: printf("%d\n", f % m); break;
        case -1: printf("%d\n", e % m); break;
        case -2: printf("%d\n", d % m); break;
        case -3: printf("%d\n", c % m); break;
        case -4: printf("%d\n", b % m); break;
        case -5: printf("%d\n", a % m); break;
        }
    }
}