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
  
  dp_A = [1] + [0] * (N + 5)
  dp_G = [1] + [0] * (N + 5)
  dp_C = [1] + [0] * (N + 5)
  dp_T = [1] + [0] * (N + 5)
  dp_AG = [0] * (N + 5)
  dp_AC = [0] * (N + 5)
  dp_GA = [0] * (N + 5)
  dp_AGA = [0] * (N + 5)
  dp_AGG = [0] * (N + 5)
  dp_AGT = [0] * (N + 5)
  dp_AAG = [0] * (N + 5)
  dp_AGG = [0] * (N + 5)
  dp_ATG = [0] * (N + 5)
  dp_ok = [4] + [0] * (N + 5)
  # ng=AGC,ACG,GAC,AG*C,A*GC
  for i in range(1, N):
      dp_A[i] = dp_ok[i - 1]
      dp_C[i] = (
          dp_ok[i - 1]
          - dp_AG[i - 1]
          - dp_GA[i - 1]
          - dp_AGG[i - 1]
          - dp_AGT[i - 1]
          - dp_ATG[i - 1]
      )
      dp_C[i] %= mod
      dp_G[i] = dp_ok[i - 1] - dp_AC[i - 1]
      dp_G[i] %= mod
      dp_T[i] = dp_ok[i - 1]
      dp_T[i] %= mod
      dp_AG[i] = dp_A[i - 1]
      dp_AG[i] %= mod
      dp_AC[i] = dp_A[i - 1] - dp_GA[i - 1]
      dp_AC[i] %= mod
      dp_GA[i] = dp_G[i - 1]
      dp_GA[i] %= mod
      dp_AGG[i] = dp_AG[i - 1]
      dp_AGG[i] %= mod
      dp_AGT[i] = dp_AG[i - 1]
      dp_AGT[i] %= mod
      dp_ATG[i] = dp_A[i - 2]
      dp_ATG[i] %= mod
      dp_ok[i] = dp_A[i] + dp_C[i] + dp_G[i] + dp_T[i]
      dp_ok[i] %= mod
  print(dp_ok[N - 1])
  
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."}]