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
  
  agc = [[1, 1, 1, 1], [4, 4, 4, 4], [16, 15, 14, 16]]
  
  for i in range(n - 3):
      sm = sum(agc[-1])
      s = sm % mod
      c = agc[-2][0] + agc[-3][0] * 2
      g = agc[-2][0] + agc[-2][2]
  
      cc, gg = sm, sm
      while cc < c:
          cc += sm
      while gg < g:
          gg += sm
      # if c > sm:
      #     c -= c // sm * sm
      # if g > sm:
      #     g -= g // sm * sm
      a = [s, (cc - c) % mod, (gg - g) % mod, s]
      # while a[1] < 0:
      #     a[1] += sm
      # while a[2] < 0:
      #     a[2] += sm
      agc.append(a)
      # print(agc)
  
  print(sum(agc[-1]))
  # [61, 51, 57, 61]
  
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."}]