#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int num,mod=;

struct matrix

{

    int a[][];

};

matrix multiply(matrix x,matrix y)//矩阵乘法

{

       matrix temp;

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

       {

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

               {

                       int ans=;

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

                       {

                               ans+=((x.a[i][k]*y.a[k][j])%mod);

                       }

                       temp.a[i][j]=ans%mod;

               }

       }

       return temp;

}

matrix calc(matrix origin,matrix answ,int n)//矩阵快速幂——answ*origin^n

{

     while(n)

     {

             if(n%==)

                    answ=multiply(origin,answ);

             origin=multiply(origin,origin);

             n/=;

     }

     return answ;

}

int main()

{

  // freopen("in.txt", "r", stdin);

  // freopen("out.txt", "w", stdout);

   int n;

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

    {

        if(n==-)break;

        matrix origin= {,,

                        ,};

        matrix answ={,,

                     ,};

        num=;

        if(n==||n==)printf("%d\n",n);

        else

        {

            answ=calc(origin,answ,n-);

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

        }

    }

    return ;

}