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 functools import lru_cache
  
  
  def check(s):
      bads = (
          ["AGC", "ACG", "GAC"]
          + ["AG{}C".format(_s) for _s in "ACGT"]
          + ["A{}GC".format(_s) for _s in "ACGT"]
      )
      return not any(map(lambda x: x in s, bads))
  
  
  def solve(string):
      n = int(string)
  
      @lru_cache(n * 4**3)
      def dfs(pos, last3):
          if pos == n:
              return 1
          ans = 0
          for _s in "ACGT":
              ans += dfs(pos + 1, last3[1:] + _s) if check(last3 + _s) else 0
          return ans % (10**9 + 7)
  
      return str(dfs(0, "TTT"))
  
  
  if __name__ == "__main__":
      print(solve(input()))
  
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."}]