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] + [0] * (n - 1)
  G = [1] + [0] * (n - 1)
  T = [1] + [0] * (n - 1)
  C = [1] + [0] * (n - 1)
  ##NG:: AGC,GAC,ACG
  AG = [0] * n
  GA = [0] * n
  AC = [0] * n
  ##NG:: AGGC,AGTC,ATGC
  AGG = [0] * n
  AGT = [0] * n
  ATG = [0] * n
  for i in range(1, n):
      tmp = A[i - 1] + G[i - 1] + C[i - 1] + T[i - 1]
  
      A[i] = tmp % mod
      T[i] = tmp % mod
      G[i] = (tmp - AC[i - 1]) % mod
      C[i] = (tmp - AG[i - 1] - GA[i - 1] - AGG[i - 1] - AGT[i - 1] - ATG[i - 1]) % mod
  
      AG[i] = A[i - 1]
      GA[i] = G[i - 1]
      AC[i] = (A[i - 1] - GA[i - 1]) % mod
  
      AGG[i] = AG[i - 1]
      AGT[i] = AG[i - 1]
      ATG[i] = A[i - 2]  # == AT[i-1]
  
  
  print((A[-1] + G[-1] + C[-1] + T[-1]) % mod)
  # print(A,G,C,T)
  # print(AG,GA,AC)
  # print(AGG,AGT,ATG)
  
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."}]