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.util.Scanner;

public class Main {

	public static void main(String[] args) {
		long prime = 1000000007L;
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		long[][] dp = new long[n+1][10];
		dp[0][0] = 1;
		for(int i=0;i<n;i++) {
			dp[i+1][0] = (dp[i][0]*2 + dp[i][2]*2 + dp[i][4]*2 + dp[i][5]*2+ dp[i][7] + dp[i][8] + dp[i][9])%prime; //その他
			dp[i+1][1] = (dp[i][0] + dp[i][1] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][9])%prime; //A
			dp[i+1][2] = (dp[i][0] + dp[i][2] + dp[i][7] + dp[i][8] + dp[i][9])%prime; //G
			dp[i+1][3] = (dp[i][1] + dp[i][6])%prime; //AG
			dp[i+1][4] = (dp[i][1])%prime; //AC
			dp[i+1][5] = (dp[i][1] + dp[i][6])%prime; //AT
			dp[i+1][6] = (dp[i][2] + dp[i][3] + dp[i][7] + dp[i][8])%prime; //GA
			dp[i+1][7] = (dp[i][3])%prime; //AGG
			dp[i+1][8] = (dp[i][5])%prime; //ATG
			dp[i+1][9] = (dp[i][3])%prime; //AGT
		}
		long ans = 0;
		for(int i=0;i<10;i++) {
			ans += dp[n][i];
		}
		System.out.println(ans%prime);
		in.close();
	}

}
