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())
  N += 1
  dp = []
  for l in range(N):
      L = []
      for i in range(4):
          I = []
          for j in range(4):
              J = [0, 0, 0, 0]
              I.append(J)
          L.append(I)
      dp.append(L)
  dp[0][0][0][0] = 1
  NGLIST_JKL = [
      [1, 0, 2],
      [1, 1, 2],
      [1, 2, 2],
      [1, 3, 2],
      [1, 2, 0],
      [1, 2, 1],
      [1, 2, 2],
      [1, 2, 3],
  ]
  NGLIST_KLM = [[1, 2, 3], [2, 1, 3], [1, 3, 2]]
  for i in range(N - 1):
      for j in range(4):
          for k in range(4):
              for l in range(4):
                  if not [j, k, l] in NGLIST_JKL:
                      for m in range(4):
                          if not [k, l, m] in NGLIST_KLM:
                              dp[i + 1][k][l][m] += dp[i][j][k][l]
                              dp[i + 1][k][l][m] = dp[i + 1][k][l][m] % (10**9 + 7)
                  else:
                      if j == 1 and l == 2:
                          for m in range(4):
                              if m != 3:
                                  dp[i + 1][k][l][m] += dp[i][j][k][l]
                                  dp[i + 1][k][l][m] = dp[i + 1][k][l][m] % (10**9 + 7)
                      elif j == 1 and k == 2:
                          for m in range(4):
                              if m != 3:
                                  dp[i + 1][k][l][m] += dp[i][j][k][l]
                                  dp[i + 1][k][l][m] = dp[i + 1][k][l][m] % (10**9 + 7)
  ans = 0
  for i in range(4):
      for j in range(4):
          for k in range(4):
              ans += dp[N - 1][i][j][k] % (10**9 + 7)
  print(ans % (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."}]