Problem: 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.

Submission attempts (in order):
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




N = int(input())
dp = [[[[0]*4]*4]*4]*(N+1)
dp[0][3][3][3] = 1
mod = 10**9+7
for n in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for now in range(4):
                    if now == 0 and i == 1 and j == 2:
                        continue
                    if now == 0 and i == 2 and j == 1:
                        continue
                    if now == 1 and i == 0 and j == 2:
                        continue
                    if now == 0 and i == 3 and j == 1 and k==2:
                        continue
                    if now == 0 and i == 1 and j == 3 and k==2:
                        continue
                    dp[n+1][now][i][j] = dp[n][i][j][k]
                    dp[n+1][now][i][j] %= mod
res = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            res += dp[N][i][j][k]
            res %= mod
   

print(res)

# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default




N = int(input())
dp = np.zeros((N+1, 4,4,4))
dp[0][3][3][3] = 1

mod = 10**9+7
for n in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if dp[n][i][j][k] == 0:
                    continue
                for now in range(4):
                    if now == 0 and i == 1 and j == 2:
                        continue
                    if now == 0 and i == 2 and j == 1:
                        continue
                    if now == 1 and i == 0 and j == 2:
                        continue
                    if now == 0 and j == 1 and k==2:
                        continue
                    if now == 0 and i == 1 and k==2:
                        continue
                    dp[n+1][now][i][j] += dp[n][i][j][k]
                    dp[n+1][now][i][j] %= mod

res = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            res += dp[N][i][j][k]
            res %= mod
   

print(int(res))

Verdicts: Wrong Answer

Accepted