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
n=int(input())
M,R=10**9+7,range(4)
dp=[[[[0]*4for k in R]for j in R]for i in range(n+1)]
dp[0][3][3][3]=1
for i in range(1,n+1):
  for j in R:
    for k in R:
      for l in R:
        for m in R:
          if(2,0,1)!=(k,l,m)!=(0,1,2)!=(k,l,m)!=(0,2,1)!=(j,l,m)!=(0,2,1)!=(j,k,m):dp[i][k][l][m]=(dp[i][k][l][m]+dp[i-1][j][k][l])%M
print(sum(c for a in dp[n]for b in a for c in b)%M)