#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define MOD 1000000007
typedef long long ll;

bool ng[1 << 8];
ll dp[101][1<<8];
string tagc = "TAGC";

bool haveAGC(string str){
	if(str.find("AGC") != string::npos)return true;
	REP(i, str.size() - 1){
		swap(str[i], str[i+1]);
		if(str.find("AGC") != string::npos)return true;
		swap(str[i], str[i+1]);
	}
	return false;
}

void makeNG() {
	REP(i, 1<<8){
		string str = "";
		int now = i;
		REP(j, 4){
			str += tagc[now % 4];
			now /= 4;
		}
		if(haveAGC(str))ng[i] = true;
	}
}

int main(){
	
	makeNG();
	int n;cin >> n;
		
	dp[0][0] = 1;
	REP(i, n){
		REP(j, 1<<8){
			REP(k, 4){
				int nxt = ((j << 2) + k) & ((1 << 8) - 1);
				if(!ng[nxt]){
					dp[i+1][nxt] += dp[i][j];
					dp[i+1][nxt] %= MOD;
				}
			}
		}
	}
		
	ll ans = 0;
	REP(i, 1<<8)ans = (ans + dp[n][i]) % MOD;
	cout << ans << endl;
	
	return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define MOD 1000000007
typedef long long ll;

bool ng[1 << 8];
ll dp[101][1<<8];
string tagc = "TAGC";

bool haveAGC(string str){
	if(str.find("AGC") != string::npos)return true;
	REP(i, str.size() - 1){
		swap(str[i], str[i+1]);
		if(str.find("AGC") != string::npos)return true;
		swap(str[i], str[i+1]);
	}
	return false;
}

void makeNG() {
	REP(i, 1<<8){
		string str = "";
		int now = i;
		REP(j, 4){
			str += tagc[now % 4];
			now /= 4;
		}
		if(haveAGC(str))ng[i] = true;
	}
}

int main(){
	
	makeNG();
	int n;cin >> n;
		
	dp[0][0] = 1;
	REP(i, n){
		REP(j, 1<<8){
			REP(k, 4){
				int nxt = ((j << 2) + k) & ((1 << 8) - 1);
				if(!ng[nxt]){
					dp[i+1][nxt] += dp[i][j];
					dp[i+1][nxt] %= MOD;
				}
			}
		}
	}
		
	ll ans = 0;
	REP(i, 1<<8)ans = (ans + dp[n][i]) % MOD;
	cout << ans << endl;
	
	return 0;
}

```