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())
  
  k = 2
  f = [1, 4, 16]
  r = [
      {"AG": 0, "GA": 0, "AC": 0, "AGG": 0, "A": 0, "G": 0},
      {"AG": 0, "GA": 0, "AC": 0, "AGG": 0, "A": 1, "G": 1},
      {"AG": 1, "GA": 1, "AC": 1, "AGG": 0, "A": 4, "G": 4, "ATG": 0, "AGT": 0, "AT": 1},
  ]
  while k < n:
      k += 1
      r.append({})
      r[k]["AC"] = r[k - 1]["A"] - r[k - 1]["GA"]
      r[k]["GA"] = r[k - 1]["G"]
      r[k]["AG"] = r[k - 1]["A"]
      r[k]["AGG"] = r[k - 1]["AG"]
      r[k]["A"] = f[k - 1]
      r[k]["G"] = f[k - 1] - r[k - 1]["AC"]
      r[k]["ATG"] = r[k - 1]["AT"]
      r[k]["AT"] = r[k - 1]["A"]
      r[k]["AGT"] = r[k - 1]["AG"]
      f.append(0)
      f[k] = (
          f[k - 1] * 4
          - r[k - 1]["AG"]
          - r[k - 1]["GA"]
          - r[k - 1]["AC"]
          - r[k - 1]["AGG"]
          - r[k - 1]["ATG"]
          - r[k - 1]["AGT"]
      )
  print(f[n] % (10**9 + 7))
  
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."}]