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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1000000007;
int dp[111][256];
int p[256];
//AGCT
int main(void) {
    int n; scanf("%d",&n);
    if (n==3) {printf("61\n"); return 0; }
    for (int j=0;j<256;j++) p[j]=1;
    for (int j=0;j<4;j++)
        p[16+4*j+2]=p[16*j+6]=p[64*j+6]=p[64*j+9]=p[64*j+18]=p[24+j]=p[36+j]=p[72+j]=0;
    for (int j=0;j<256;j++) dp[4][j]=p[j];
    for (int i=5;i<=n;i++) {
        for (int j=0;j<256;j++) if (p[j]) {
            for (int k=j/4;k<256;k+=64) {
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod;
            }
        }
    }
    int ans=0;
    for (int j=0;j<256;j++) ans = (ans+dp[n][j]) % mod;
    printf("%d\n",ans);
    return 0;
}


//AGC ACG GAC
//012 021 102
//AGXC AXGC
//01X2 0X12
