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())
  dp = [dict() for i in range(2)]
  
  big = 10**9 + 7
  
  for a in ["A", "C", "G", "T"]:
      for b in ["A", "C", "G", "T"]:
          for c in ["A", "C", "G", "T"]:
              seq = a + b + c
              if seq != "AGC" and seq != "GAC" and seq != "ACG":
                  dp[0][seq] = 1
              else:
                  dp[0][seq] = 0
  
  
  def sum_of_dict(d):
      ans = 0
      for a in ["A", "C", "G", "T"]:
          for b in ["A", "C", "G", "T"]:
              for c in ["A", "C", "G", "T"]:
                  seq = a + b + c
                  ans += d[seq]
      return ans
  
  
  def sum_of_dict_with(d, latter):
      ans = 0
      for a in ["A", "C", "G", "T"]:
          seq = a + latter
          ans += d[seq]
      return ans
  
  
  for i in range(3, N):
      n = i % 2
      for a in ["A", "C", "G", "T"]:
          for b in ["A", "C", "G", "T"]:
              for c in ["A", "C", "G", "T"]:
                  seq = a + b + c
                  if seq == "AGC" or seq == "GAC" or seq == "ACG":
                      dp[n][seq] = 0
                  elif seq == "TGC":
                      dp[n][seq] = (
                          sum_of_dict_with(dp[(n - 1) % 2], seq[:2])
                          - dp[(n - 1) % 2]["ATG"]
                      ) % big
                  elif seq == "GGC":
                      dp[n][seq] = (
                          sum_of_dict_with(dp[(n - 1) % 2], seq[:2])
                          - dp[(n - 1) % 2]["AGG"]
                      ) % big
                  elif seq == "GTC":
                      dp[n][seq] = (
                          sum_of_dict_with(dp[(n - 1) % 2], seq[:2])
                          - dp[(n - 1) % 2]["AGT"]
                      ) % big
                  else:
                      dp[n][seq] = (sum_of_dict_with(dp[(n - 1) % 2], seq[:2])) % big
  
  print(sum_of_dict(dp[(N - 1) % 2]) % big)
  
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."}]