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: #!/usr/bin/env python
  # coding: utf-8
  
  # In[1]:
  
  
  N = int(input())
  
  
  # In[14]:
  
  
  # N = 4
  MOD = 10**9 + 7
  
  
  # In[15]:
  
  
  char = ["A", "C", "G", "T"]
  S = [c1 + c2 + c3 for c1 in char for c2 in char for c3 in char]
  S
  
  
  # In[16]:
  
  
  ng3 = ["AGC", "GAC", "ACG"]
  ng4 = (
      [c + ng for c in char for ng in ng3]
      + [ng + c for c in char for ng in ng3]
      + ["A" + c + "GC" for c in char]
      + ["AG" + c + "C" for c in char]
  )
  ng4 = set(ng4)
  ng4
  
  
  # In[17]:
  
  
  dict1 = {s: 1 if s not in ng3 else 0 for s in S}
  
  
  # In[18]:
  
  
  for _ in range(N - 3):
      dict2 = {}
  
      for s in S:
          val = 0
          for c in char:
              if c + s not in ng4:
                  val = (val + dict1[c + s[:2]]) % MOD
          dict2[s] = val
      dict1 = dict2
  
  
  # In[19]:
  
  
  ans = 0
  for s in dict1.keys():
      ans = (ans + dict1[s]) % MOD
  print(ans)
  
  
  # In[ ]:
  
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."}]