You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

* The string does not contain characters other than `A`, `C`, `G` and `T`.
* The string does not contain `AGC` as a substring.
* The condition above cannot be violated by swapping two adjacent characters once.

Constraints

* 3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:


N


Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Examples

Input

3


Output

61


Input

4


Output

230


Input

100


Output

388130742
#include<bits/stdc++.h>
using namespace std;
int n, f[105], vis[105][5][5][5][5], a[105][5][5][5][5];
#define ll long long
const int mod=1e9+7;
int dfs(int k){
	if(k>=3) {
		if(f[k-3]==1&&f[k-2]==2&&f[k-1]==3) return 0;
		if(f[k-4]==1&&f[k-2]==2&&f[k-1]==3) return 0;
		if(f[k-4]==1&&f[k-3]==2&&f[k-1]==3) return 0;
		if(f[k-3]==1&&f[k-2]==3&&f[k-1]==2) return 0;
		if(f[k-3]==2&&f[k-2]==1&&f[k-1]==3) return 0;
	}
	if(k==n+1){
		return 1;
	}
	ll s=0;
	for(int i=1;i<=4;i++){
		f[k]=i;
		if(vis[k][f[k-3]][f[k-2]][f[k-1]][i]) s+=a[k][f[k-3]][f[k-2]][f[k-1]][i];
		else s+=(a[k][f[k-3]][f[k-2]][f[k-1]][i]=dfs(k+1));
		vis[k][f[k-3]][f[k-2]][f[k-1]][i]=1;
		s%=mod;
		f[k]=0;
	}
	return s;
}
int main(){
	cin>>n;
	cout<<dfs(1);
}
