#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
const int mod=1e9+7;

ll dp[100][4][4][4];

int main(){
  int n;
  cin >> n;
  dp[0][3][3][3]=1;
  rep(i,n){
    rep(j,4){
      rep(k,4){
        rep(l,4){
          rep(m,4){
            if(k==0&&l==1&&m==2 || k==1&&l==0&&m==2 || k==0&&l==2&&m==1 ||j==0&&l==1&&m==2|| j==0&&k==1&&m==2)
              continue;
            dp[i+1][k][l][m]+=dp[i][j][k][l];
            dp[i+1][k][l][m]%=mod;
          }
        }
      }
    }
  }
  ll sum=0;
  rep(i,4){
    rep(j,4){
      rep(k,4){
        sum+=dp[n][i][j][k];
        sum%=mod;
      }
    }
  }
  cout << sum << endl;
  return 0;
}
### Prompt

Create a solution in CPP for 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<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
const int mod=1e9+7;

ll dp[100][4][4][4];

int main(){
  int n;
  cin >> n;
  dp[0][3][3][3]=1;
  rep(i,n){
    rep(j,4){
      rep(k,4){
        rep(l,4){
          rep(m,4){
            if(k==0&&l==1&&m==2 || k==1&&l==0&&m==2 || k==0&&l==2&&m==1 ||j==0&&l==1&&m==2|| j==0&&k==1&&m==2)
              continue;
            dp[i+1][k][l][m]+=dp[i][j][k][l];
            dp[i+1][k][l][m]%=mod;
          }
        }
      }
    }
  }
  ll sum=0;
  rep(i,4){
    rep(j,4){
      rep(k,4){
        sum+=dp[n][i][j][k];
        sum%=mod;
      }
    }
  }
  cout << sum << endl;
  return 0;
}
```