#include <bits/stdc++.h>
#include <vector>
using namespace std;
const long mod=1000000007;
int main(){
    int n;
    cin>>n;
    vector<long>ans(n+1),ag(n+1),ac(n+1),ga(n+1),at(n+1),a(n+1),g(n+1),c(n+1),t(n+1);
    ans[1]=4;
    ans[2]=16;
    ag[1]=ac[1]=ga[1]=0;
    ag[2]=ac[2]=ga[2]=at[2]=1;
    a[2]=g[2]=c[2]=t[2]=4;
    for(int i = 3; i <= n; i++){
        a[i]=ans[i-1];
        g[i]=ans[i-1]-ac[i-1];
        c[i]=ans[i-1]-ag[i-1]-ga[i-1]-ag[i-2]*2-at[i-2];
        t[i]=ans[i-1];
        ag[i]=a[i-1];
        ac[i]=a[i-1]-ga[i-1];
        ga[i]=g[i-1];
        at[i]=a[i-1];
        ans[i]=((a[i]+g[i]+c[i]+t[i])%mod+mod)%mod;
    }
    cout<<ans[n]<<endl;
}
### 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 <bits/stdc++.h>
#include <vector>
using namespace std;
const long mod=1000000007;
int main(){
    int n;
    cin>>n;
    vector<long>ans(n+1),ag(n+1),ac(n+1),ga(n+1),at(n+1),a(n+1),g(n+1),c(n+1),t(n+1);
    ans[1]=4;
    ans[2]=16;
    ag[1]=ac[1]=ga[1]=0;
    ag[2]=ac[2]=ga[2]=at[2]=1;
    a[2]=g[2]=c[2]=t[2]=4;
    for(int i = 3; i <= n; i++){
        a[i]=ans[i-1];
        g[i]=ans[i-1]-ac[i-1];
        c[i]=ans[i-1]-ag[i-1]-ga[i-1]-ag[i-2]*2-at[i-2];
        t[i]=ans[i-1];
        ag[i]=a[i-1];
        ac[i]=a[i-1]-ga[i-1];
        ga[i]=g[i-1];
        at[i]=a[i-1];
        ans[i]=((a[i]+g[i]+c[i]+t[i])%mod+mod)%mod;
    }
    cout<<ans[n]<<endl;
}
```