#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=1e9+7;

int n,f[105][64];
int main(){
	scanf("%d",&n);
	if(n==1){
		puts("4");
		return 0;
	}
	if(n==2){
		puts("16");
		return 0;
	}
	if(n==3){
		puts("61");
		return 0;
	}
	for(int i=0;i<4;i++)
	for(int j=0;j<4;j++)
	for(int k=0;k<4;k++)
		f[3][i*16+j*4+k]=1;
	f[3][11]=f[3][35]=f[3][14]=0;
	for(int i=4;i<=n;i++)
	for(int j=0;j<64;j++){
		int x=j/16,y=(j%16)/4,z=j%4;
		(f[i][y*16+z*4]+=f[i-1][j])%=P;
		(f[i][y*16+z*4+1]+=f[i-1][j])%=P;
		if(!(y==0&&z==3))(f[i][y*16+z*4+2]+=f[i-1][j])%=P;
		if((y==2&&z==0)||(y==0&&z==2)||(x==0&&z==2)||(x==0&&y==2));
		else (f[i][y*16+z*4+3]+=f[i-1][j])%=P;
	}
	int ans=0;
	for(int i=0;i<64;i++)
		ans=(ans+f[n][i])%P;
	printf("%d",ans);
}
/*
A 0
T 1
G 2
C 3
AGC
GAC
ACG

A*GC
AG*C
*AGC
*GAC
*ACG
*/
### Prompt

Please provide a CPP coded solution to the problem described below:

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;
const int N=1e5+5,P=1e9+7;

int n,f[105][64];
int main(){
	scanf("%d",&n);
	if(n==1){
		puts("4");
		return 0;
	}
	if(n==2){
		puts("16");
		return 0;
	}
	if(n==3){
		puts("61");
		return 0;
	}
	for(int i=0;i<4;i++)
	for(int j=0;j<4;j++)
	for(int k=0;k<4;k++)
		f[3][i*16+j*4+k]=1;
	f[3][11]=f[3][35]=f[3][14]=0;
	for(int i=4;i<=n;i++)
	for(int j=0;j<64;j++){
		int x=j/16,y=(j%16)/4,z=j%4;
		(f[i][y*16+z*4]+=f[i-1][j])%=P;
		(f[i][y*16+z*4+1]+=f[i-1][j])%=P;
		if(!(y==0&&z==3))(f[i][y*16+z*4+2]+=f[i-1][j])%=P;
		if((y==2&&z==0)||(y==0&&z==2)||(x==0&&z==2)||(x==0&&y==2));
		else (f[i][y*16+z*4+3]+=f[i-1][j])%=P;
	}
	int ans=0;
	for(int i=0;i<64;i++)
		ans=(ans+f[n][i])%P;
	printf("%d",ans);
}
/*
A 0
T 1
G 2
C 3
AGC
GAC
ACG

A*GC
AG*C
*AGC
*GAC
*ACG
*/
```