#if 1

#include <bits/stdc++.h>
using namespace std;
int n;
map <string,long long> d[105];
int a[5] = {'A','C','G','T'};

int ok(string s)
{
    for(int i = 0;i < 4;i++)
    {
        string s2 = s;
        if(i != 0)
        {
            char s3 = s2[i];
            s2[i] = s2[i-1];
            s2[i-1] = s3;
        }
        if(s2.substr(0,3) == "AGC"||s2.substr(1) == "AGC") return 0;
    }
    return 1;
}

long long dfs(int x,string s)
{
    if(d[x].count(s))
    {
        return d[x][s];
    }
    if(x == n) return 1;
    long long ans = 0;
    for(int i = 0;i < 4;i++)
    {
        char y = a[i];
        if(ok(s+y)) ans += dfs(x+1,s.substr(1)+y);
    }
    d[x][s] = ans%1000000007;
    return d[x][s];
}

int main()
{
    cin >> n;
    cout << dfs(0,"TTT");
}

#endif // 1++
### Prompt

Your task is to create a CPP solution 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
#if 1

#include <bits/stdc++.h>
using namespace std;
int n;
map <string,long long> d[105];
int a[5] = {'A','C','G','T'};

int ok(string s)
{
    for(int i = 0;i < 4;i++)
    {
        string s2 = s;
        if(i != 0)
        {
            char s3 = s2[i];
            s2[i] = s2[i-1];
            s2[i-1] = s3;
        }
        if(s2.substr(0,3) == "AGC"||s2.substr(1) == "AGC") return 0;
    }
    return 1;
}

long long dfs(int x,string s)
{
    if(d[x].count(s))
    {
        return d[x][s];
    }
    if(x == n) return 1;
    long long ans = 0;
    for(int i = 0;i < 4;i++)
    {
        char y = a[i];
        if(ok(s+y)) ans += dfs(x+1,s.substr(1)+y);
    }
    d[x][s] = ans%1000000007;
    return d[x][s];
}

int main()
{
    cin >> n;
    cout << dfs(0,"TTT");
}

#endif // 1++
```