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())
  ans = 0
  M = (10**9) + 7
  dic = {}
  pdic = {}
  pdic["AAA"] = 1
  pdic["AAC"] = 1
  pdic["AAG"] = 1
  pdic["AAT"] = 1
  pdic["ACA"] = 1
  pdic["ACC"] = 1
  pdic["ACG"] = 0
  pdic["ACT"] = 1
  pdic["AGA"] = 1
  pdic["AGC"] = 0
  pdic["AGG"] = 1
  pdic["AGT"] = 1
  pdic["ATA"] = 1
  pdic["ATC"] = 1
  pdic["ATG"] = 1
  pdic["ATT"] = 1
  pdic["CAA"] = 1
  pdic["CAC"] = 1
  pdic["CAG"] = 1
  pdic["CAT"] = 1
  pdic["CCA"] = 1
  pdic["CCC"] = 1
  pdic["CCG"] = 1
  pdic["CCT"] = 1
  pdic["CGA"] = 1
  pdic["CGC"] = 1
  pdic["CGG"] = 1
  pdic["CGT"] = 1
  pdic["CTA"] = 1
  pdic["CTC"] = 1
  pdic["CTG"] = 1
  pdic["CTT"] = 1
  pdic["GAA"] = 1
  pdic["GAC"] = 0
  pdic["GAG"] = 1
  pdic["GAT"] = 1
  pdic["GCA"] = 1
  pdic["GCC"] = 1
  pdic["GCG"] = 1
  pdic["GCT"] = 1
  pdic["GGA"] = 1
  pdic["GGC"] = 1
  pdic["GGG"] = 1
  pdic["GGT"] = 1
  pdic["GTA"] = 1
  pdic["GTC"] = 1
  pdic["GTG"] = 1
  pdic["GTT"] = 1
  pdic["TAA"] = 1
  pdic["TAC"] = 1
  pdic["TAG"] = 1
  pdic["TAT"] = 1
  pdic["TCA"] = 1
  pdic["TCC"] = 1
  pdic["TCG"] = 1
  pdic["TCT"] = 1
  pdic["TGA"] = 1
  pdic["TGC"] = 1
  pdic["TGG"] = 1
  pdic["TGT"] = 1
  pdic["TTA"] = 1
  pdic["TTC"] = 1
  pdic["TTG"] = 1
  pdic["TTT"] = 1
  for i in range(N - 3):
      for k in pdic.keys():
          k = str(k)
          if k == "ACG" or k == "AGC" or k == "GAC":
              dic[k] = 0
          elif k[1:] == "GC":
              dic[k] = pdic["C" + k[:-1]] + pdic["G" + k[:-1]] + pdic["T" + k[:-1]]
          elif k[0] == "G" and k[2] == "C":
              dic[k] = pdic["C" + k[:-1]] + pdic["G" + k[:-1]] + pdic["T" + k[:-1]]
          else:
              dic[k] = (
                  pdic["A" + k[:-1]]
                  + pdic["C" + k[:-1]]
                  + pdic["G" + k[:-1]]
                  + pdic["T" + k[:-1]]
              )
      for k in pdic.keys():
          pdic[k] = dic[k]
  if N == 3:
      print(61)
  else:
      for v in dic.values():
          ans += v
          ans = ans % M
      print(ans)
  
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."}]