/*
* @Author: Administrator
* @Date:   2017-08-31 17:40:04
* @Last Modified by:   Administrator
* @Last Modified time: 2017-09-01 11:03:00
*/
/*
 题意：给你一个4*n的矩阵，然后让你用1*2和2*1的木块放，问你完美覆盖的
    方案数

 思路：状压DP找规律
*/

#include <bits/stdc++.h>

#define MAXN 100
#define MAXM 20
#define MAXK 15
using namespace std;

int dp[MAXN][MAXM];//dp[i][j]表示前ihang 
int n;

inline bool ok(int x){
    //判断是不是有连续个1的个数是奇数
    int res=0;
    while(x){
        if(x%2==1){
            res++;
        }else{
            if(res%2==1) return false;
            else res=0;
        }
        x/=2;
    }
    if(res%2==1) return false;
    else return true;
}

inline void init(){
    memset(dp,0,sizeof dp);
}

int main(){
    freopen("in.txt","r",stdin);
    for(int n=1;n<=50;n++){
        init();
        for(int i=0;i<=MAXK;i++){//初始化第一行的没种状态
            if(ok(i)==true)
                dp[1][i]=1;
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<=MAXK;j++){
                if(dp[i][j]!=0){
                    for(int k=0;k<=MAXK;k++){
                        if( (j|k)==MAXK && ok(j&k) )
                            ///j|k==tot-1的话就是能拼起来组成
                            dp[i+1][k]+=dp[i][j];
                    }
                }
            }
        }
        printf("%d\n",dp[n][MAXK]);
    }
    return 0;
}

/*
* @Author: Administrator
* @Date:   2017-09-01 11:17:37
* @Last Modified by:   Administrator
* @Last Modified time: 2017-09-01 11:28:09
*/
#include <bits/stdc++.h>

#define MAXN 5
#define mod 1000000007
#define LL long long

using namespace std;

/********************************矩阵快速幂**********************************/
class Matrix {
    public:
        LL a[MAXN][MAXN];
        LL n;  

        void init(LL x) {
            memset(a,0,sizeof(a));
            if (x)  
                for (int i = 0; i < MAXN ; i++)
                    a[i][i] = 1LL;
        }
        
        Matrix operator +(Matrix b) {
            Matrix c;
            c.n = n;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    c.a[i][j] = (a[i][j] + b.a[i][j]) % mod;
            return c;
        }

        Matrix operator +(LL x) {
            Matrix c = *this;
            for (int i = 0; i < n; i++)
                c.a[i][i] += x;
            return c;
        }

        Matrix operator *(Matrix b)
        {
            Matrix p;
            p.n = b.n;   
            p.init(0);
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    p.a[i][j] = (p.a[i][j] + (a[i][k]*b.a[k][j])%mod) % mod;
            return p;
        }

        Matrix power(LL t) {
            Matrix ans,p = *this;
            ans.n = p.n;  
            ans.init(1);
            while (t) {
                if (t & 1)
                    ans=ans*p;
                p = p*p;
                t >>= 1;
            }
            return ans;
        }
}init,unit;
/********************************矩阵快速幂**********************************/

LL n;

int main(){
    // freopen("in.txt","r",stdin);
    while(scanf("%lld",&n)!=EOF){
        if(n<=4){
            switch(n){
                case 1:
                    puts("1");
                    break;
                case 2:
                    puts("5");
                    break;
                case 3:
                    puts("11");
                    break;
                case 4:
                    puts("36");
                    break;
            }
            continue;
        }
        init.init(0);
        init.n=4;
        init.a[0][0]=36;
        init.a[0][1]=11;
        init.a[0][2]=5;
        init.a[0][3]=1;
        unit.init(0);
        unit.n=4;
        unit.a[0][0]=1;
        unit.a[1][0]=5;
        unit.a[2][0]=1;
        unit.a[3][0]=-1;
        unit.a[0][1]=1;
        unit.a[1][2]=1;
        unit.a[2][3]=1;
        unit=unit.power(n-4);
        init=init*unit;
        printf("%lld\n",(init.a[0][0]+mod)%mod);
    }
    return 0;
}