#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include<math.h>

using namespace std;

#define N 10

struct node

{

    int a[N][N];

}s,e;

node mul(node p, node q)///求两个矩阵的积；

{

    node tem;

    for(int i=; i<; i++)

    {

        for(int j=; j<; j++)

        {

            tem.a[i][j] = ;

            for(int k=; k<; k++)

                tem.a[i][j] = (tem.a[i][j]+p.a[i][k]*q.a[k][j])%;

        }

    }

    return tem;

}

node Pow(node p, int n)

{

    node tem;

    for(int i=; i<; i++)

        for(int j=; j<; j++)

            tem.a[i][j] = (i==j);

    while(n)

    {

        if(n&)///n是奇数；

            tem = mul(tem, p);///让矩阵e和矩阵a相乘；

        n/=;

        p = mul(p, p);

    }

    return tem;

}

int main()

{

    s.a[][] = ;

    s.a[][] = ;

    s.a[][] = ;

    s.a[][] = ;

    int n;

    while(scanf("%d", &n),n!=-)

    {

        e = Pow(s, n);

        printf("%d\n", e.a[][]);

    }

    return ;

}