#include <bits/stdc++.h>

using namespace std;

#define gc getchar()

#define LL long long

const LL mod = ;

LL n, s;

inline LL read(){

    LL x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

struct Node{

    LL m[][];

    Node() { memset(m,,sizeof m);}

    void clear(){for(int i = ; i <= n; i ++) m[i][i] = ;}

};

Node operator *(Node a, Node b){

    Node ret;

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

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

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

                ret.m[i][j] = (ret.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;

    return ret;

}

Node ksm(Node a, LL p){

    Node ret; ret.clear();

    while(p){

        if(p & ) ret = ret * a;

        a = a * a;

        p >>= ;

    }

    return ret;

}

int main()

{

     s = read();

     s += ;

    n = ;

    Node a, b;

    a.m[][] = ; a.m[][] = ; a.m[][] = ; a.m[][] = ;

    b.m[][] = ; b.m[][] = ;

    Node Ans;

    Ans = ksm(a, s - );

    Node answer = Ans * b;

    cout << answer.m[][] - ;

    return ;

}