#include<iostream>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int Mod=;

 struct mat{

     ll a[][];

 };

 mat mat_mul(mat x,mat y){

     mat ans;

     memset(ans.a,,sizeof(ans.a));

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

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

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

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

     }

     return ans;

 }

 ll mat_pow(ll n){

     mat c,res;

     c.a[][]=c.a[][]=c.a[][]=;

     c.a[][]=;

     memset(res.a,,sizeof(res.a));

     for (int i=;i<;i++) res.a[i][i]=;

     while (n){

         if (n&) res=mat_mul(res,c);

         c=mat_mul(c,c);

         n>>=;

     }

     return res.a[][]%Mod;

 }

 int main(){

     ll n;

     while (cin >> n && n!=-){

         cout << mat_pow(n) << endl;

     }

     return ;

 }