#include <cstdio>

const int prim = 1048576;

const int MAX_N = 15;

int N;

int c[MAX_N];

inline int next(int pos, int cnt) {
    return (pos + cnt) % 10;
}

int main() {

    freopen("12perm.in", "r", stdin);
    freopen("12perm.out", "w", stdout);

    scanf("%d", &N);

    if (N == 1)
        printf("1\n");
    if (N == 2)
        printf("2\n");
    if (N == 3)
        printf("6\n");
    if (N > 3) {
        c[0] = 1;
        for (int ind = 0; ind < N; ind++) {
            int i = ind % 10;
            c[next(i, 1)] = (c[next(i, 1)] + c[i]) % prim;
            c[next(i, 2)] = (c[next(i, 2)] + c[i]) % prim;
            if (i == N - 3)
                c[next(i, 3)] = (c[next(i, 3)] + c[i]) % prim;

            c[i] = 0;
        }

        printf("%d\n", c[N % 10] * 2);
    }

    return 0;
}