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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main
{
	static HashMap<String, Long>[] DP;
	static String Chars = "ACGT";
	
	static boolean isValid(String Last)
	{
		for (int i = 0; i < Last.length(); i++)
		{
			String temp = Last;
			if (i >= 1)
			{
				temp = "";
				for (int j = 0; j < i - 1; j++)
				{
					temp += Last.charAt(j);
				}
				temp += Last.charAt(i) + "" + Last.charAt(i - 1);
				for (int j = i + 1; j < Last.length(); j++)
				{
					temp += Last.charAt(j);
				}
			}
			if (temp.contains("AGC"))
			{
				return false;
			}
		}
		return true;
	}
	
	static long DFS(int N, String Last)
	{
		if (DP[N].containsKey(Last))
		{
			return DP[N].get(Last);
		}
		if (N == 0) return 1;
		DP[N].put(Last, 0l);
		for (int i = 0; i < Chars.length(); i++)
		{
			if (isValid(Last + Chars.charAt(i)))
			{
				long prev = DP[N].get(Last);
				DP[N].put(Last, (prev + DFS(N - 1, Last.substring(1) + Chars.charAt(i))) % ((int)1e9 + 7));
			}
		}
		return DP[N].get(Last);
	}
	
	public static void main(String[] Arguments) throws IOException 
	{
		BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(BR.readLine()); DP = new HashMap[N + 1];
		for (int i = 0; i <= N; i++)
		{
			DP[i] = new HashMap<>();
		}
		System.out.println(DFS(N, "TTT"));
	}
}
