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>
#define int long long
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF LLONG_MAX
#define eps LDBL_EPSILON
#define moder 1000000007
#define pie 3.141592653589793238462643383279
#define P std::pair<int,int>
#define prique priority_queue
#define ggr getchar();getchar();return 0
using namespace std;
int n;
int dp[110][4][4][4];
signed main() {
	cin>>n;
	dp[0][3][3][3]=1;
	rep(i,n){
		rep(j,4){
			rep(k,4){
				rep(l,4){
					rep(m,4){
						if(i==0||i==1||(!(k==0&&l==2&&m==1)&&!(k==2&&l==0&&m==1)&&!(k==0&&l==1&&m==2)&&!(j==0&&l==2&&m==1)&&!(j==0&&k==2&&m==1)))dp[i+1][k][l][m]+=dp[i][j][k][l];
						dp[i+1][k][l][m]%=moder;
					}
				}
			}
		}
	}
	int ans=0;
	rep(i,4){
		rep(j,4){
			rep(k,4)ans+=dp[n][i][j][k];
			ans%=moder;
		}
	}
	cout<<ans<<endl;
}