output_description: Print the number of strings of length N that satisfy the following conditions,
  modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: n = int(input())
  mod = 10**9 + 7
  a = [1] * 16
  no = [0, 0]
  for _ in range(n - 2):
      b = [0] * 16
      b[0] = a[0] + a[4] + a[8] + a[12]
      b[1] = a[0] + a[4] + a[12]
      b[2] = a[0] + a[4] + a[8] + a[12]
      b[3] = a[0] + a[4] + a[8] + a[12]
      b[4] = a[1] + a[5] + a[9] + a[13]
      b[5] = a[1] + a[5] + a[9] + a[13]
      b[6] = a[5] + a[9] + a[13]
      b[7] = a[1] + a[5] + a[9] + a[13]
      b[8] = a[2] + a[6] + a[9] + a[14]
      b[9] = a[6] + a[9] + a[14] - no[0] - no[1]
      b[10] = a[2] + a[6] + a[9] + a[14]
      b[11] = a[2] + a[6] + a[9] + a[14]
      b[12] = a[3] + a[7] + a[10] + a[15]
      b[13] = a[3] + a[7] + a[10] + a[15] - no[1]
      b[14] = a[3] + a[7] + a[10] + a[15]
      b[15] = a[3] + a[7] + a[10] + a[15]
      no[0] = a[2]
      no[1] = a[3]
      a = b
      for i in range(16):
          a[i] %= mod
  print(sum(a))
  
problem_description: Statement
  
  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.
samples: [{"input": "3", "output": "61\n    \n\nThere are 4^3 = 64 strings of length 3 that do not contain characters other\nthan `A`, `C`, `G` and `T`. Among them, only `AGC`, `ACG` and `GAC` violate\nthe condition, so the answer is 64 - 3 = 61.\n\n* * *"}, {"input": "4", "output": "230\n    \n\n* * *"}, {"input": "100", "output": "388130742\n    \n\nBe sure to print the number of strings modulo 10^9+7."}]