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())
  AA = [0] * (N + 1)
  AG = [0] * (N + 1)
  AC = [0] * (N + 1)
  GG = [0] * (N + 1)
  GA = [0] * (N + 1)
  GC = [0] * (N + 1)
  CC = [0] * (N + 1)
  CA = [0] * (N + 1)
  CG = [0] * (N + 1)
  T_ = [0] * (N + 1)
  _T = [0] * (N + 1)
  TT = [0] * (N + 1)
  
  AA[2], AG[2], AC[2], GG[2], GA[2], GC[2], CC[2], CA[2], CG[2], T_[2], _T[2], TT[2] = (
      1,
      1,
      1,
      1,
      1,
      1,
      1,
      1,
      1,
      3,
      3,
      1,
  )
  for i in range(3, N + 1):
      AA[i] = AA[i - 1] + GA[i - 1] + CA[i - 1] + T_[i - 1] // 3
      AG[i] = AA[i - 1] + GA[i - 1] + CA[i - 1] + T_[i - 1] // 3
      AC[i] = AA[i - 1] + CA[i - 1] + T_[i - 1] // 3
      GG[i] = AG[i - 1] + GG[i - 1] + CG[i - 1] + T_[i - 1] // 3
      GA[i] = AG[i - 1] + GG[i - 1] + CG[i - 1] + T_[i - 1] // 3
      GC[i] = GG[i - 1] + CG[i - 1] + T_[i - 1] // 3 - AG[i - 2] - _T[i - 2] // 3
      CC[i] = AC[i - 1] + GC[i - 1] + CC[i - 1] + T_[i - 1] // 3
      CA[i] = AC[i - 1] + GC[i - 1] + CC[i - 1] + T_[i - 1] // 3
      CG[i] = GC[i - 1] + CC[i - 1] + T_[i - 1] // 3
      T_[i] = _T[i - 1] * 3 + TT[i - 1] * 3 - AG[i - 2]
      _T[i] = (
          AA[i - 1]
          + AG[i - 1]
          + AC[i - 1]
          + GG[i - 1]
          + GA[i - 1]
          + GC[i - 1]
          + CC[i - 1]
          + CA[i - 1]
          + CG[i - 1]
          + T_[i - 1]
      )
      TT[i] = _T[i - 1] + TT[i - 1]
  
  ans = (
      AA[N]
      + AG[N]
      + AC[N]
      + GG[N]
      + GA[N]
      + GC[N]
      + CC[N]
      + CA[N]
      + CG[N]
      + T_[N]
      + _T[N]
      + TT[N]
  )
  print(ans % (10**9 + 7))
  print(
      AA[N], AG[N], AC[N], GG[N], GA[N], GC[N], CC[N], CA[N], CG[N], T_[N], _T[N], TT[N]
  )
  
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."}]