#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
using ll=long long;

ll dp[110][4][4][4];//A0 C1 G2 T3

ll dfs(int size,int i,int j,int k){
  if(dp[size][i][j][k]!=-1) return dp[size][i][j][k];
  if(size==3){
    if(i==0 && j==1 && k==2) return dp[3][i][j][k]=0;
    if(i==0 && j==2 && k==1) return dp[3][i][j][k]=0;
    if(i==1 && j==0 && k==2) return dp[3][i][j][k]=0;
    return dp[3][i][j][k]=1;
  }
  ll sum=0;
  for(int l=0;l<4;l++){
    if(i==0 && j==1 && k==2) continue;
    if(i==0 && j==2 && k==1) continue;
    if(i==1 && j==0 && k==2) continue;
    if(i==0 && k==1 && l==2) continue;
    if(i==0 && j==1 && l==2) continue;
    sum+=dfs(size-1,j,k,l);
    sum%=MOD;
  }
  
  return dp[size][i][j][k]=sum;
}

int main(){
  int n; cin>>n;
  memset(dp, -1, sizeof(dp));
  cout<<dfs(n+3, 3, 3, 3)<<endl;
}
### Prompt

In cpp, your task is to solve the following problem:

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 MOD=1000000007;
using ll=long long;

ll dp[110][4][4][4];//A0 C1 G2 T3

ll dfs(int size,int i,int j,int k){
  if(dp[size][i][j][k]!=-1) return dp[size][i][j][k];
  if(size==3){
    if(i==0 && j==1 && k==2) return dp[3][i][j][k]=0;
    if(i==0 && j==2 && k==1) return dp[3][i][j][k]=0;
    if(i==1 && j==0 && k==2) return dp[3][i][j][k]=0;
    return dp[3][i][j][k]=1;
  }
  ll sum=0;
  for(int l=0;l<4;l++){
    if(i==0 && j==1 && k==2) continue;
    if(i==0 && j==2 && k==1) continue;
    if(i==1 && j==0 && k==2) continue;
    if(i==0 && k==1 && l==2) continue;
    if(i==0 && j==1 && l==2) continue;
    sum+=dfs(size-1,j,k,l);
    sum%=MOD;
  }
  
  return dp[size][i][j][k]=sum;
}

int main(){
  int n; cin>>n;
  memset(dp, -1, sizeof(dp));
  cout<<dfs(n+3, 3, 3, 3)<<endl;
}
```