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
import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int N = Integer.parseInt(str);
        long mod = 1_000_000_007;
        long[][][][] dp = new long[N+1][4][4][4];
        dp[0][3][3][3] = 1;
        for (int len=0;len<N;len++){
            for (int c1=0;c1<4;c1++){
                for (int c2=0;c2<4;c2++){
                    for (int c3=0;c3<4;c3++){
                        if (dp[len][c1][c2][c3]==0){
                            continue;
                        }
                        for (int a=0;a<4;a++){
                            if (a==2 && c1==1 && c2==0){
                                continue;
                            } else if (a==2 && c1==0 && c2==1){
                                continue;
                            } else if (a==1 && c1==2 && c2==0){
                                continue;
                            } else if (a==2 && c1==1 && c3==0){
                                continue;
                            } else if (a==2 && c2==1 && c3==0){
                                continue;
                            }
                            dp[len+1][a][c1][c2] += dp[len][c1][c2][c3];
                            dp[len+1][a][c1][c2] %= mod;
                        }
                    }
                }
            }
        }
        long ans = 0;
        for (int c1=0;c1<4;c1++){
            for (int c2=0;c2<4;c2++){
                for (int c3=0;c3<4;c3++){
                    ans += dp[N][c1][c2][c3];
                }
            }
        }
        System.out.println(ans%=mod);
    }
}