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) {
		Main main = new Main();
		main.solve();
	}

	void solve() {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		sc.close();
		int[][][][] dp = new int[101][4][4][4];
		dp[0][3][3][3] = 1;
		int Mod = 1000_000_007;

		//文字列の文字数
		for (int len = 0; len < n; len++)
		{
			//最後から1文字目の文字
			for (int c1 = 0; c1 < 4; c1++)
			{
				//最後から2文字目の文字
				for (int c2 = 0; c2 < 4; c2++)
				{
					//最後から3文字目の文字
					for (int c3 = 0; c3 < 4; c3++)
					{
						//条件に当てはまるものがない場合はcontinue;
						if (dp[len][c1][c2][c3] == 0) continue;

						//新しく追加する文字
						for (int a = 0; a < 4; a++)
						{
							//ダメな5つの条件をカットする
							if (a == 2 && c1 == 1 && c2 == 0) continue;
							if (a == 2 && c1 == 0 && c2 == 1) continue;
							if (a == 1 && c1 == 2 && c2 == 0) continue;
							if (a == 2 && c1 == 1 && c3 == 0) continue;
							if (a == 2 && c2 == 1 && c3 == 0) continue;

							//ダメな条件を抜けたら、aを足した文字列が作れる

							// S = ...... c3 c2 c1
							// nextS = ...... c2 c1 a

							dp[len + 1][a][c1][c2] += dp[len][c1][c2][c3];
							if(dp[len + 1][a][c1][c2]>Mod)dp[len + 1][a][c1][c2] -= Mod;
						}
					}
				}
			}
		}

		int res = 0;

		//長さNの全部の答えを纏める
		//最後から1文字目の文字
		for (int c1 = 0; c1 < 4; c1++)
		{
			//最後から2文字目の文字
			for (int c2 = 0; c2 < 4; c2++)
			{
				//最後から3文字目の文字
				for (int c3 = 0; c3 < 4; c3++)
				{
					res += dp[n][c1][c2][c3];
					if(res > Mod)res-=Mod;
				}
			}
		}
		System.out.println(res);
	}

}