/*少说话,多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
//#include<bits/stdc++.h>
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
typedef long long ll;
using namespace std;
/*
*/
const int maxn = 3;
const ll mod=1e9+7;
struct node
{
ll m[maxn][maxn];
}unit;
void init() //初始化 ,将unit设为单位数组
{
for(int i=0;i<maxn;i++)
{
for (int j=0;j<maxn;j++)
{
if(i==j) unit.m[i][j]=1;
else unit.m[i][j]=0;
}
}
}
node matmul(node a,node b) //定义矩阵的乘法 -> 矩阵乘以矩阵,返回的是矩阵
{
node ans;
ll tmp =0;
for(int i=0;i<maxn;i++)
{
for(int j=0;j<maxn;j++)
{
tmp=0;
for(int k=0;k<maxn;k++)
{
tmp=(tmp + a.m[i][k] * b.m[k][j])%mod;
}
ans.m[i][j]=tmp;
}
}
return ans;
}
node qaq (node x , ll n) //计算数组^b, --》比如设A为数组,B为一个数,则qaq求的是A^B
{
init(); //将unit初始化为单位矩阵 ,一开始都是从单位矩阵开始乘的。 -》 就一直按照unit变化,最后得出的答案就是从unit中找,这道题是m[1][0]为fn
while(n!=0)
{
if(n%2==1) //如果b是奇数
{
unit = matmul(unit, x); //ans是矩阵,unit也是矩阵
}
x = matmul(x, x);
n>>=1;
}
return unit;
}
int main()
{
ll n;
while(cin >> n)
{
if(n==1) cout << "1" << endl;
else if(n==2) cout << "2" << endl;
else if(n==3) cout << "4" << endl;
else
{
node x = {1,1,1,1,0,0,0,1,0};
x = qaq(x, n-3);
cout << (x.m[0][0]*4%mod + x.m[0][1]*2%mod + x.m[0][2]*1%mod)%mod << endl;
}
}
return 0;
}