using System; using static System.Console; using System.Linq; using System.Collections.Generic; using AtCoder; class Program { public static void Main() { Solve(); } static void Solve() { var n = long.Parse(ReadLine()); var a = new long[][] { [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0] }; var x = new long[][] { [1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1], [1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1], [1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1] }; var b = Matrix.Mul(a, Matrix.Pow(x, n - 1)); WriteLine((b[0][0] + b[0][1] + b[0][2] + b[0][3] + b[0][4] + b[0][6] + b[0][8] + b[0][10]) % mod); } // visualizer static void OutputLeft(int id, List[] text) { if (new int[] { 0, 4, 6, 8 }.Contains(id)) { text[0].Add('-'); text[0].Add('-'); } if (new int[] { 1, 10 }.Contains(id)) { text[2].Add('-'); text[2].Add('-'); } if (new int[] { 2, 5 }.Contains(id)) { text[4].Add('-'); text[4].Add('-'); } if (new int[] { 3, 7, 9, 11 }.Contains(id)) { text[6].Add('-'); text[6].Add('-'); } if (new int[] { 5, 7 }.Contains(id)) { text[0].Add('+'); text[0].Add('-'); text[1].Add('|'); text[2].Add('+'); text[2].Add('-'); } if (id == 9) { text[0].Add('+'); text[0].Add('-'); text[1].Add('|'); text[2].Add('|'); text[3].Add('|'); text[4].Add('+'); text[4].Add('-'); } if (id == 4 || id == 11) { text[2].Add('+'); text[2].Add('-'); text[3].Add('|'); text[4].Add('+'); text[4].Add('-'); } if (id == 6) { text[2].Add('+'); text[2].Add('-'); text[3].Add('|'); text[4].Add('|'); text[5].Add('|'); text[6].Add('+'); text[6].Add('-'); } if (id == 8 || id == 10) { text[4].Add('+'); text[4].Add('-'); text[5].Add('|'); text[6].Add('+'); text[6].Add('-'); } for (var i = 0; i < 7; ++i) { while (text[i].Count < 2) text[i].Add(' '); if (i % 2 == 0) text[i].Add('O'); else text[i].Add(' '); } } static void OutputRight(int id, List[] text) { if (new int[] { 0, 4, 6, 8 }.Contains(id)) { text[0].Add('-'); text[0].Add('-'); } if (new int[] { 1, 10 }.Contains(id)) { text[2].Add('-'); text[2].Add('-'); } if (new int[] { 2, 5 }.Contains(id)) { text[4].Add('-'); text[4].Add('-'); } if (new int[] { 3, 7, 9, 11 }.Contains(id)) { text[6].Add('-'); text[6].Add('-'); } if (new int[] { 5, 7 }.Contains(id)) { text[0].Add('-'); text[0].Add('+'); text[1].Add(' '); text[1].Add('|'); text[2].Add('-'); text[2].Add('+'); } if (id == 9) { text[0].Add('-'); text[0].Add('+'); text[1].Add(' '); text[1].Add('|'); text[2].Add(' '); text[2].Add('|'); text[3].Add(' '); text[3].Add('|'); text[4].Add('-'); text[4].Add('+'); } if (id == 4 || id == 11) { text[2].Add('-'); text[2].Add('+'); text[3].Add(' '); text[3].Add('|'); text[4].Add('-'); text[4].Add('+'); } if (id == 6) { text[2].Add('-'); text[2].Add('+'); text[3].Add(' '); text[3].Add('|'); text[4].Add(' '); text[4].Add('|'); text[5].Add(' '); text[5].Add('|'); text[6].Add('-'); text[6].Add('+'); } if (id == 8 || id == 10) { text[4].Add('-'); text[4].Add('+'); text[5].Add(' '); text[5].Add('|'); text[6].Add('-'); text[6].Add('+'); } } static int mod = 1_000_000_007; class Matrix { // 行列の累乗 public static long[][] Pow(long[][] m, long k) { var multi = m; var r = new long[m.Length][]; for (var i = 0; i < m.Length; ++i) { r[i] = new long[m.Length]; r[i][i] = 1; } while (k > 0) { if ((k & 1) == 1) r = Mul(r, multi); multi = Mul(multi, multi); k >>= 1; } return r; } // 行列の積 public static long[][] Mul(long[][] x, long[][] y) { var r = new long[x.Length][]; for (var i = 0; i < x.Length; ++i) r[i] = new long[y[0].Length]; for (var i = 0; i < x.Length; ++i) for (var k = 0; k < x[0].Length; ++k) { for (var j = 0; j < y[0].Length; ++j) r[i][j] = (r[i][j] + x[i][k] * y[k][j]) % mod; } return r; } } }