#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int buf[105];
inline void print(int x,char ch=' '){
	if(x<0) putchar('-'),x=-x;
	int tot=0;
	do{
		buf[++tot]=x%10;
		x/=10;
	}while(x);
	for(int i=tot;i;i--) putchar(buf[i]+'0');
	putchar(ch);
}
const int MAXN=4,mod=1e9+7;
struct matrix{
	int m[MAXN][MAXN];
	matrix(){
		memset(m,0,sizeof(m));
	}
	int *operator[](const int &x){
		return m[x];
	}
	matrix friend operator*(matrix a,matrix b){
		matrix c;
		for(int i=0;i<MAXN;i++)
			for(int k=0;k<MAXN;k++)
				for(int j=0;j<MAXN;j++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
		return c;
	}
};
int n;
matrix qpow(matrix a,int b){
	matrix ans=matrix(),base=a;
	for(int i=0;i<MAXN;i++) ans[i][i]=1;
	while(b){
		if(b&1) ans=ans*base;
		base=base*base;
		b>>=1;
	}
	return ans;
}
signed main(){
	while(cin>>n){
		if(n==1) print(1,'\n');
		else if(n==2) print(2,'\n');
		else if(n==3) print(6,'\n');
		else{
			matrix f,g;
			f[0][0]=16,f[0][1]=6,f[0][2]=2,f[0][3]=2;
			
			g[0][0]=2,g[2][0]=1,g[3][0]=1;
			g[0][1]=1;
			g[1][2]=1;
			g[3][3]=1;
			
			f=f*qpow(g,n-4);
			print(f[0][0],'\n');
		}
	}
	return 0;
}