#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

ll dp[110][4][4][4];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  dp[0][3][3][3]=1;
  rep(i,n)rep(j,4)rep(k,4)rep(l,4)rep(x,4){
    if(k==0 && l==2 && x==1) continue;
    if(k==0 && l==1 && x==2) continue;
    if(k==2 && l==0 && x==1) continue;
    if(j==0 && k==2 && x==1) continue;
    if(j==0 && l==2 && x==1) continue;
    (dp[i+1][k][l][x]+=dp[i][j][k][l])%=mod;
  }
  ll ans=0;
  rep(j,4)rep(k,4)rep(l,4) (ans+=dp[n][j][k][l])%=mod;
  cout<<ans<<endl;
}
### Prompt

Please create a solution in Cpp to 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;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

ll dp[110][4][4][4];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  dp[0][3][3][3]=1;
  rep(i,n)rep(j,4)rep(k,4)rep(l,4)rep(x,4){
    if(k==0 && l==2 && x==1) continue;
    if(k==0 && l==1 && x==2) continue;
    if(k==2 && l==0 && x==1) continue;
    if(j==0 && k==2 && x==1) continue;
    if(j==0 && l==2 && x==1) continue;
    (dp[i+1][k][l][x]+=dp[i][j][k][l])%=mod;
  }
  ll ans=0;
  rep(j,4)rep(k,4)rep(l,4) (ans+=dp[n][j][k][l])%=mod;
  cout<<ans<<endl;
}
```