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 = [[0] * 16 for _ in range(N + 1)]
  for i in range(16):
      dp[2][i] = 1
  for n in range(3, N + 1):
      for f in range(4):
          for s in range(4):
              if f == 0 and s == 1:
                  dp[n][s * 4 + 0] = (dp[n][s * 4 + 0] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 1] = (dp[n][s * 4 + 1] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 3] = (dp[n][s * 4 + 3] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
              elif f == 0 and s == 2:
                  dp[n][s * 4 + 0] = (dp[n][s * 4 + 0] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 2] = (dp[n][s * 4 + 2] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 3] = (dp[n][s * 4 + 3] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
              elif f == 2 and s == 0:
                  dp[n][s * 4 + 0] = (dp[n][s * 4 + 0] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 2] = (dp[n][s * 4 + 2] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 3] = (dp[n][s * 4 + 3] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
              else:
                  dp[n][s * 4 + 0] = (dp[n][s * 4 + 0] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 1] = (dp[n][s * 4 + 1] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 2] = (dp[n][s * 4 + 2] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
                  dp[n][s * 4 + 3] = (dp[n][s * 4 + 3] + dp[n - 1][f * 4 + s]) % (
                      10**9 + 7
                  )
  print(sum(dp[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."}]