#include <cstdio>

#include <algorithm>

#include <cstring>

#define int long long

using namespace std;

const int MOD = ;

int n;

struct Matrix{

  static const int MAXN = ;

  int alpha[MAXN][MAXN];

  int n,m;

  void init(void){

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

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

        alpha[i][j]=;

    n=m=;

  }

  void init_f2(void){

    n=;m=;

    alpha[][]=;

    alpha[][]=;

    alpha[][]=;

    alpha[][]=;

  }

  void init_f(void){

    n=;m=;

    alpha[][]=;

    alpha[][]=;

  }

  void init_pow(int x){

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

      alpha[i][i]=;

    m=n=x;

  }

  Matrix operator * (Matrix b){

    Matrix c;

    c.init();

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

      for(int j=;j<=b.m;j++)

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

          c.alpha[i][j]=(c.alpha[i][j]%MOD+alpha[i][k]*b.alpha[k][j]%MOD)%MOD;

    c.n=n;

    c.m=b.m;

    return c;

  }

};

Matrix pow(Matrix a,int p){

  Matrix ans;

  ans.init();

  ans.init_pow(a.n);

  while(p){

    if(p&)

      ans=ans*a;

    a=a*a;

    p>>=;

  }

  return ans;

}

signed main(){

  scanf("%lld",&n);

  Matrix f,f2,ans;

  f.init();

  f.init_f();

  f2.init();

  f2.init_f2();

  ans=pow(f2,n-);

//  for(int i=1;i<=ans.n;i++){

//    for(int j=1;j<=ans.m;j++)

//      printf("%d ",ans.alpha[i][j]);

//    printf("\n");

//    }

  f=f*ans;

  printf("%lld",f.alpha[][]%MOD);

  return ;

}