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

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)
  {
    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);
  
  }
}
