import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Scanner; import javax.swing.plaf.metal.OceanTheme; public class Main { public static void main(String[] args) throws FileNotFoundException { new Main().run(); } void run() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); long n = sc.nextLong(); ArrayList list = new ArrayList<>(); HashMap, Integer> index = new HashMap<>(); int idx = 0; for (int i = 0; i <= 2; ++i) { for (int j = 0; j <= 2; ++j) { for (int k = 0; k <= 2; ++k) { for (int l = 0; l <= 2; ++l) { if (!ok(new int[] { i, j, k, l })) continue; list.add(new int[] { i, j, k, l }); index.put(Arrays.asList(i, j, k, l), idx); ++idx; } } } } long[][] mat = new long[16][16]; // mat[x][y]=x->yへの遷移数 for (int i = 0; i < list.size(); ++i) { int[] cur = list.get(i); ArrayDeque pend = new ArrayDeque<>(); ArrayDeque pend2 = new ArrayDeque<>(); pend.add(cur); pend2.add(cur); mat[index.get(toList(cur))][index.get(toList(cur))]++; while (!pend.isEmpty()) { int[] p = pend.pollFirst(); int src = -1; for (int j = 0; j < 4; ++j) if (p[j] == 1) src = j; // 1を移動 for (int d = -1; d <= 1; d += 2) { int nsrc = src + d; if (!(0 <= nsrc && nsrc <= 3) || p[nsrc] == -1) continue; int[] dst = Arrays.copyOf(p, p.length); dst[nsrc] = 1; dst[src] = -1; for (int j = 0; j < 4; ++j) { if (dst[j] == 2 && p[nsrc] == 2) { dst[j] = 1; dst[nsrc] = -1; } } if (!ok(dst)) { throw new AssertionError(); } pend.add(dst); pend2.add(dst); dst = regulate(dst); mat[index.get(toList(dst))][index.get(toList(cur))]++; } // 2を伸ばす while (!pend2.isEmpty()) { int[] p2 = pend2.poll(); for (int j = 0; j < 4; ++j) { if (p2[j] != 2) continue; for (int d = -1; d <= 1; d += 2) { int nj = j + d; if (!(0 <= nj && nj < 4) || p2[nj] != 0) { continue; } int[] dst = Arrays.copyOf(p2, p2.length); dst[j] = -1; dst[nj] = 2; if (!ok(dst)) { throw new AssertionError(); } pend2.add(dst); dst = regulate(dst); mat[index.get(toList(dst))][index.get(toList(cur))]++; } } } // 2を生成 for (int j = 0; j < 4; ++j) { loop: for (int k = j + 1; k < 4; ++k) { for (int l = j; l <= k; ++l) { if (p[l] != 0) continue loop; } int[] dst = Arrays.copyOf(p, p.length); for (int l = j; l <= k; ++l) { dst[l] = -1; } dst[j] = 2; dst[k] = 2; if (!ok(dst)) { throw new AssertionError(); } dst = regulate(dst); mat[index.get(toList(dst))][index.get(toList(cur))]++; } } } } long[][] v = new long[16][1]; int curIdx = index.get(Arrays.asList(1, 0, 0, 0)); int lastIdx = index.get(Arrays.asList(0, 0, 0, 1)); v[curIdx][0]++; v = mul(pow(mat, n + 1), v); System.out.println(v[lastIdx][0]); } boolean ok(int[] arr) { int c2 = count(2, 0, 3, arr); if (!(c2 == 0 || c2 == 2)) return false; int c1 = count(1, 0, 3, arr); if (c1 != 1) return false; for (int i = 0; i < 4; ++i) { if (arr[i] != 2) continue; for (int j = i + 1; j < 4; ++j) { if (arr[j] != 2) continue; for (int k = i + 1; k < j; ++k) { if (arr[k] == 1) return false; } } } return true; } int count(int val, int s, int t, int[] arr) { int ret = 0; for (int i = s; i <= t; ++i) { if (arr[i] == val) ++ret; } return ret; } int count(int val, int s, int t, List list) { int ret = 0; for (int i = 0; i < 4; ++i) { if (list.get(i) == val) { ++ret; } } return ret; } long[][] mul(long[][] a, long[][] b) { long[][] ret = new long[a.length][b[0].length]; for (int i = 0; i < a.length; ++i) { for (int j = 0; j < b[i].length; ++j) { for (int k = 0; k < a[0].length; ++k) { ret[i][j] += a[i][k] * b[k][j] % MODULO; ret[i][j] %= MODULO; } } } return ret; } long[][] pow(long[][] a, long n) { long[][] ret = new long[a.length][a.length]; for (int i = 0; i < a.length; ++i) { ret[i][i] = 1; } for (; n > 0; n >>= 1, a = mul(a, a)) { if (n % 2 == 1) { ret = mul(ret, a); } } return ret; } ArrayList toList(int[] arr) { ArrayList ret = new ArrayList<>(); for (int i = 0; i < arr.length; ++i) { ret.add(arr[i]); } return ret; } int[] regulate(int[] arr) { int[] ret = Arrays.copyOf(arr, arr.length); for (int i = 0; i < arr.length; ++i) { if (ret[i] == -1) ret[i] = 0; } return ret; } int[] regulate(ArrayList arr) { int[] ret = new int[arr.size()]; for (int i = 0; i < arr.size(); ++i) { if (arr.get(i) == -1) ret[i] = 0; else ret[i] = arr.get(i); } return ret; } final long MODULO = 1_000_000_000 + 7; static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }