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;
typedef long long ll;
const ll mod = 1e9+7;
ll dp[101][4][4][4];

int main(){
	int N;
	cin >> N;
	dp[0][3][3][3] = 1;
	for(int len=0; len<N; len++){
		for(int c1=0; c1<4; c1++){
			for(int c2=0; c2<4; c2++){
				for(int c3=0; c3<4; c3++){
					for(int c4=0; c4<4; c4++){
						if(c2 == 0 && c3 == 1 && c4 == 2) continue;
						if(c2 == 1 && c3 == 0 && c4 == 2) continue;
						if(c2 == 0 && c3 == 2 && c4 == 1) continue;
						if(c1 == 0 && c3 == 1 && c4 == 2) continue;
						if(c1 == 0 && c2 == 1 && c4 == 2) continue;
						dp[len+1][c2][c3][c4] += dp[len][c1][c2][c3];
						dp[len+1][c2][c3][c4] %= mod;
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			for(int k=0; k<4; k++){
				ans += dp[N][i][j][k];
			}
		}
	}
	ans %= mod;
	cout << ans << endl;
	return 0;
}