#include<stdio.h>
#include<stdlib.h>

unsigned int calcF(int n){
    unsigned int *F, *P, *Q, *R, result;
    int i;
    F = (unsigned int *)malloc((n+1)*sizeof(unsigned int));
    P = (unsigned int *)malloc((n+1)*sizeof(unsigned int));
    Q = (unsigned int *)malloc((n+1)*sizeof(unsigned int));
    R = (unsigned int *)malloc((n+1)*sizeof(unsigned int));

    F[0] = F[1] = 1;
    P[0] = P[1] = 0;
    Q[0] = Q[1] = 0;
    R[0] = R[1] = 0;

    for (i = 2; i <= n; i++) {
        F[i] = (2*F[i-1] + 9*F[i-2] + 2*P[i-2] + 2*Q[i-2] + 2*R[i-2]) % 10000000;
        P[i] = (2*P[i-1] +12*F[i-2] + 9*P[i-2] + 6*Q[i-2] + 4*R[i-2]) % 10000000;
        Q[i] = (2*Q[i-1] +20*F[i-2] +10*P[i-2] + 9*Q[i-2] + 4*R[i-2]) % 10000000;
        R[i] = (2*R[i-1] +30*F[i-2] +10*P[i-2] + 6*Q[i-2] + 9*R[i-2]) % 10000000;
    }
    result = F[n];

    free(F);
    free(P);
    free(Q);
    free(R);
    return result;
}

int main(void){
    unsigned long long i;
    unsigned long F;
    char str[1024];
    while( fgets(str, sizeof(str), stdin) != NULL ){
        i = strtoull(str, NULL, 0);
        F = calcF(i % 6000000);
        printf("%d\n", F);
    }
    return 0;
}