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

public class Main {

	static HashMap<String, Long> DP[];
	static String Chars = "ACGT";

	static boolean isValid(String S) {
		if (S.contains("AGC")) {
			return false;
		}
		for (int i = 1; i < S.length(); i++) {
			String temp = "";
			for (int j = 0; j < i - 1; j++) {
				temp += S.charAt(j);
			}
			temp += S.charAt(i) + "" + S.charAt(i - 1);
			for (int j = i + 1; j < S.length(); j++) {
				temp += S.charAt(j);
			}
			if (temp.contains("AGC")) {
				return false;
			}
		}
		return true;
	}

	static long DFS(int N, String cur) // N is the remaining length of string; cur is the last 3 characters of the
										// current string
	{
		if (DP[N].containsKey(cur)) {
			return DP[N].get(cur);
		}
		if (N == 0)
			return 1;
		DP[N].put(cur, 0l);
		for (int i = 0; i < Chars.length(); i++) {
			if (isValid(cur + Chars.charAt(i))) {
				long prev = DP[N].get(cur);
				long result = DFS(N - 1, cur.substring(1) + Chars.charAt(i));
				int MOD = (int) 1e9 + 7;
				DP[N].put(cur, (prev + result) % MOD);
			}
		}
		return DP[N].get(cur);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		DP = new HashMap[N + 1];
		for (int i = 0; i <= N; i++) {
			DP[i] = new HashMap<>();
		}
		long result = DFS(N, "TTT");
		System.out.println(result);

	}

}
