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: from collections import defaultdict
  
  n = int(input())
  MOD = 10**9 + 7
  
  s = "ATGC"
  t = ["AGC", "ACG", "GAC"]
  # d = [defaultdict(int), {x+y+z: 1 for x in s for y in s for z in s if x+y+z not in t}]
  d = [{"": 1}, defaultdict(int)]
  
  # print(d[0])
  for i in range(1, n + 1):
      a = i % 2
      b = (i - 1) % 2
  
      d[a] = defaultdict(int)
      for k in d[b]:
          for c in s:
              if len(k) < 2:
                  d[a][k + c] += d[b][k]
                  d[a][k + c] %= MOD
              elif len(k) == 2:
                  if "AGC" not in [k + c, k[1] + k[0] + c, k[0] + c + k[1]]:
                      d[a][k + c] += d[b][k]
                      d[a][k + c] %= MOD
              elif "AGC" not in [
                  k[1:] + c,
                  k[0] + k[2] + c,
                  k[2] + k[1] + c,
                  k[1] + c + k[2],
                  k[0] + k[1] + c,
              ]:
                  # if len(set(k+c)) >= 3:
                  #     print(k+c)
                  d[a][k[1:] + c] += d[b][k]
                  d[a][k[1:] + c] %= MOD
      # print(len(d[a]), sum(d[a].values()))
      # print(d[a])
  
  print(sum(d[n % 2].values()))
  
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."}]