Problem:
 Score : 400 points    Problem 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.       Notes A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T .  For example, the substrings of ATCODER include TCO , AT , CODER , ATCODER and (the empty string), but not AC .      Constraints  3 \leq N \leq 100         Input Input is given from Standard Input in the following format:  N       Output Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7 .        Sample Input 1 3      Sample Output 1 61  There are 4^3 = 64 strings of length 3 that do not contain characters other than A , C , G and T . Among them, only AGC , ACG and GAC violate the condition, so the answer is 64 - 3 = 61 .       Sample Input 2 4      Sample Output 2 230       Sample Input 3 100      Sample Output 3 388130742  Be sure to print the number of strings modulo 10^9+7 .

Solution (Python):
MOD=10**9+7
N=int(input())
if N==3:
  print(61)
  exit()
  
dp=[[[[1]*4 for c in range(4)] for b in range(4)] for a in range(4)]
        
for x in range(4):
  dp[0][x][2][1]=0
  dp[0][2][x][1]=0
  dp[0][1][2][x]=0
  dp[2][0][1][x]=0
  dp[0][2][1][x]=0
  dp[x][0][1][2]=0
  dp[x][2][0][1]=0
  dp[x][0][2][1]=0
  
def f():
  tmp=[[[[0]*4 for c in range(4)] for b in range(4)] for a in range(4)]
  for a in range(4):
    for b in range(4):
      for c in range(4):
        t=sum([dp[x][a][b][c] for x in range(4)])
        t%=MOD
        for d in range(4):
          tmp[a][b][c][d]=t
          
  for x in range(4):
    tmp[0][x][2][1]=0
    tmp[0][2][x][1]=0
    tmp[x][0][1][2]=0
    tmp[x][2][0][1]=0
    tmp[x][0][2][1]=0
    
  return tmp
  
for k in range(4, N):
  dp=f()
  
print(sum([dp[a][b][c][d] for a in range(4) for b in range(4) for c in range(4) for d in range(4)])%MOD)

Solution (Python):
MOD=10**9+7
N=int(input())
if N==3:
  print(61)
  exit()
  
dp=[[[[1]*4 for c in range(4)] for b in range(4)] for a in range(4)]
        
for x in range(4):
  dp[0][x][2][1]=0
  dp[0][2][x][1]=0
  dp[0][1][2][x]=0
  dp[2][0][1][x]=0
  dp[0][2][1][x]=0
  dp[x][0][1][2]=0
  dp[x][2][0][1]=0
  dp[x][0][2][1]=0
  
def f():
  tmp=[[[[0]*4 for c in range(4)] for b in range(4)] for a in range(4)]
  for a in range(4):
    for b in range(4):
      for c in range(4):
        t=sum([dp[x][a][b][c] for x in range(4)])
        t%=MOD
        for d in range(4):
          tmp[a][b][c][d]=t
          
  for x in range(4):
    tmp[0][x][2][1]=0
    tmp[0][2][x][1]=0
    tmp[0][1][2][x]=0
    tmp[2][0][1][x]=0
    tmp[0][2][1][x]=0
    tmp[x][0][1][2]=0
    tmp[x][2][0][1]=0
    tmp[x][0][2][1]=0
    
  return tmp
  
for k in range(4, N):
  dp=f()
  
print(sum([dp[a][b][c][d] for a in range(4) for b in range(4) for c in range(4) for d in range(4)])%MOD)

Solution (Python):
import numpy as np
MOD = 10**9+7
n = int(input())
dp = np.zeros((n+1, 4, 4, 4), dtype=np.int64)
dp[0, 3, 3, 3] = 1
for i in range(n):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for d in range(4):
          if d==1:
            if (a==0 and b==2) or (a==0 and c==2) or (b==0 and c==2) or (c==0 and b==2):
              continue
          if b==0 and d==2 and c==1:
            continue
          dp[i+1, b, c, d] += dp[i, a, b, c]
          dp[i+1, b, c, d] %= MOD
print(dp[n].sum()%MOD)

Solution (Python):
p = 10**9+7
N = int(input())
dp = [[[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not(j==0 and k==1 and l==2) and not(j==0 and k==2 and l==1) and not(j==1 and k==0 and l==2):
                dp[3][0][j][k][l] = 1
for n in range(4,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if not(j==0 and k==1 and l==2) and not(j==0 and k==2 and l==1) and not(j==1 and k==0 and l==2) \
                    and not(i==0 and k==1 and l==2) and not(i==0 and j==1 and l==2):
                        dp[n][i][j][k][l] = 0
                        for m in range(4):
                            dp[n][i][j][k][l] = (dp[n][i][j][k][l]+dp[n-1][m][i][j][k])%p
tot = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                tot = (tot + dp[N][i][j][k][l])%p
print(tot)

Solution (Python):
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def ok(W):
    if W.count("AGC") >= 1:
        return False

    for i in range(1, 4):
        L = list(W)
        L[i - 1], L[i] = L[i], L[i - 1]
        if "".join(L).count("AGC") >= 1:
            return False
    return True


def main():
    mod = 10 ** 9 + 7
    dp = {}
    W = "ACGT"
    for a in W:
        for b in W:
            for c in W:
                w = a + b + c
                if w in ("AGC", "ACG", "GAC"):
                    continue
                dp[w] = 1

    N = int(input())
    for n in range(N - 3):
        dp2 = {}
        for a in dp.keys():
            for b in W:
                if ok(a + b):
                    w = a[1:] + b
                    dp2[w] = (dp[a] + dp2.setdefault(w, 0)) % mod
        dp.update(dp2)
    print(sum(v for v in dp.values()) % mod)


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
mod=10**9+7


A=5
dp=[[[[0]*A for _ in range(A)] for _ in range(A)] for _ in range(N+1)]

def check1(a,b,c):
    t=[a,b,c]
    if t==[1,2,4] or t==[1,4,2] or t==[2,1,4]:
        return False
    return True

def check2(a,b,c,m):
    if ([b,c]==[2,4] and m==1) or ([a,c]==[2,4] and m==1):
        return False
    return check1(a,b,c)
    
    

for n in range(min(4,N+1)):
    for i in range(A):
        for j in range(A):
            for k in range(A):
                if check1(i,j,k):
                    dp[n][i][j][k]=1
                    
for n in range(4,N+1):
    for i in range(1,A):
        for j in range(1,A):
            for k in range(1,A):
                for m in range(1,A):
                    if check2(i,j,k,m):
                        dp[n][i][j][k]+=dp[n-1][m][i][j]
                dp[n][i][j][k]%=mod
                        
ans=0
if N>=3:
    for i in range(1,A):
            for j in range(1,A):
                for k in range(1,A):
                    ans+=dp[N][i][j][k]

if N==1:
    ans=4
elif N==2:
    ans=16

print(ans%mod)

Solution (Python):
N=int(input())
mod=10**9+7


A=5
dp=[[[[0]*A for _ in range(A)] for _ in range(A)] for _ in range(N+1)]

def check1(a,b,c):
    t=[a,b,c]
    if t==[1,2,4] or t==[1,4,2] or t==[2,1,4]:
        return False
    return True

def check2(a,b,c,m):
    if ([b,c]==[2,4] and m==1) or ([a,c]==[2,4] and m==1):
        return False
    return check1(a,b,c)
    
    

for n in range(min(4,N+1)):
    for i in range(A):
        for j in range(A):
            for k in range(A):
                if check1(i,j,k):
                    dp[n][i][j][k]=1
                    
for n in range(4,N+1):
    for i in range(1,A):
        for j in range(1,A):
            for k in range(1,A):
                for m in range(1,A):
                    if check2(i,j,k,m):
                        dp[n][i][j][k]+=dp[n-1][m][i][j]
                dp[n][i][j][k]%=mod
                        
ans=0
if N>=4:
    for i in range(1,A):
            for j in range(1,A):
                for k in range(1,A):
                    ans+=dp[N][i][j][k]

if N==1:
    ans=4
elif N==2:
    ans=16
elif N==3:
    ans=61

print(ans%mod)

Solution (Python):
n=int(input())
A,G,C,T,mod,ans=0,1,2,3,pow(10,9)+7,0
dp=[[[[0]*4for k in range(4)]for j in range(4)]for i in range(n+1)]
dp[0][T][T][T]=1
for i in range(1,n+1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        for m in range(4):
          if(G,A,C)!=(k,l,m)!=(A,C,G)!=(k,l,m)!=(A,G,C)!=(j,l,m)!=(A,G,C)!=(j,k,m):
            dp[i][k][l][m]+=dp[i-1][j][k][l]
            dp[i][k][l][m]%=mod
for j in range(4):
  for k in range(4):
    for l in range(4):
      ans+=dp[n][j][k][l]
print(ans%mod)

Solution (Python):
N = int(input())

DIVIDER = 1000000007

memo = [{} for _ in range(N + 1)]

tab_pow4 = [1]
tab_tmp = 1
for i in range(N):
    tab_tmp *= 4
    tab_pow4.append(tab_tmp)

def dp(Nlen, end):
    if Nlen < len(end):
        return 0
    elif memo[Nlen].setdefault(end, None) != None:
        return memo[Nlen][end]
    
    if end in ('AGC', 'GAC', 'ACG'):
        ret = 0
    elif Nlen == len(end):
        ret = 1
    else:
        ret = 0
        if end not in ('AGC', 'TGC', 'CGC', 'GGC', 'GAC', 'GTC', 'GCC', 'GGC'):
            ret = (ret + dp(Nlen - 1, 'A' + end[:2])) % DIVIDER
        ret = (ret + dp(Nlen - 1, 'C' + end[:2])) % DIVIDER
        ret = (ret + dp(Nlen - 1, 'G' + end[:2])) % DIVIDER
        ret = (ret + dp(Nlen - 1, 'T' + end[:2])) % DIVIDER
    
    memo[Nlen][end] = ret
    return ret

import itertools

ans = 0
for end in itertools.product('ACGT', repeat=3):
    if end in ('AGC', 'CAG', 'ACG'): continue
    ans = (ans + dp(N, ''.join(end))) % DIVIDER



print(ans)

Solution (Python):
N = int(input())

memo = [{} for _ in range(N)]  


def judge(last):
    if last[1:] in ('AGC', 'ACG', 'GAC'):
        return False
    if last[0] == 'A':
        if last[1] == 'G' and last[-1] == 'C': return False
        if last[2] == 'G' and last[-1] == 'C': return False
    return True


MOD = 10 ** 9 + 7


def dfs(i, last):
    if i >= N:  
        return 1

    if last in memo[i]:
        return memo[i][last]

    res = 0
    for c in 'AGCT':
        l = last[1:] + c
        if judge(l):
            res += dfs(i + 1, l) % MOD
    memo[i][last] = res % MOD
    return res


print(dfs(0, 'XXXX') % MOD)

Solution (Python):
MOD = 10 ** 9 + 7
N = int(input())
memo = [{} for _ in range(N + 1)]


def isOK(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).count('AGC'):
            return False
    return True


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if isOK(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))

Solution (Python):
MOD = 10 ** 9 + 7
N = int(input())
memo = [{} for _ in range(N + 1)]


def isOK(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).count('AGC'):
            return False
    return True


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if isOK(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))

Solution (Python):
from collections import Counter


MOD = 10 ** 9 + 7


def isOK(last3, s):
    for i in range(len(last3 + s)):
        t = list(last3 + s)
        if i >= 1:
            t[i], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).count('AGC'):
            return False
    return True


S = 'ACGT'
N = int(input())
dp = [None] * (N + 1)

dp[1] = Counter()
for s1 in S:
    dp[1][s1] += 1

dp[2] = Counter()
for s1 in S:
    for s2 in S:
        dp[2][s1 + s2] += dp[1][s1]

dp[3] = Counter()
for s1 in S:
    for s2 in S:
        for s3 in S:
            if isOK(s1 + s2, s3):
                dp[3][s1 + s2 + s3] += dp[2][s1 + s2]

for i in range(4, N + 1):
    dp[i] = Counter()
    for s1 in S:
        for s2 in S:
            for s3 in S:
                for s4 in S:
                    if isOK(s1 + s2 + s3, s4):
                        dp[i][s2 + s3 + s4] += dp[i - 1][s1 + s2 + s3]
                        dp[i][s2 + s3 + s4] %= MOD

print(sum(dp[N].values()) % MOD)

Solution (Python):
n = int(input())
dp = [[0]*4 for i in range(n+1)]
mod = 10**9+7

dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 1
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = 4

for i in range(2,n):
    for j in range(4):
        dp[i][j] = sum(dp[i-1])%mod
    dp[i][1] -= dp[i-2][0]
    dp[i][2] -= (dp[i-2][0] + dp[i-2][1])
    if i >= 3:
        dp[i][2] -= 3*dp[i-3][0]
        dp[i][1] += dp[i-3][1]
        

print(sum(dp[n-1])%mod)

Solution (Python):
import sys
import re
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    def is_ok(S):
        if re.match(r'(.?(AGC|GAC|ACG).?|A(.G|G.)C)',S):
            return False
        else:
            return True
    memo=[{} for _ in range(N+1)]
    def saiki(i,last3):
        if last3 in memo[i]:
            return memo[i][last3]
        if i==N:
            return 1
        c=0
        for s in 'ATGC':
            if is_ok(last3+s):
                c+=saiki(i+1,last3[1:]+s)
                c%=MOD
        memo[i][last3]=c
        return c
    print(saiki(0,'TTT'))
            
    

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
dp = [[[[0 for _ in range(4) ]for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
MOD = 10 ** 9 + 7

dp[0][0][0][0] = 1 
A, G, C, T = 0, 1, 2, 3

for i in range(N):
    for c1 in range(4): 
        for c2 in range(4): 
            for c3 in range(4): 
                for c in range(4): 
                    if (c, c1, c2) in [(A,G,C), (G,A,C), (A,C,G)]:
                        continue
                    if (c, c2, c3) == (A,G,C):
                        continue
                    if (c, c1, c3) == (A,G,C):
                        continue
                    dp[i+1][c][c1][c2] += (dp[i][c1][c2][c3] % MOD)

ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[N][c3][c2][c1]

print(ans % MOD)

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7

memo = [{} for _ in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)

        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]

        if ''.join(t).count('AGC') >= 1:
            return False

    return True


def dfs(cur, last3):
    global N, MOD, memo

    if last3 in memo[cur]:
        return memo[cur][last3]

    if cur == N:
        return 1

    ret = 0
    for c in 'AGCT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD

    memo[cur][last3] = ret

    return ret


print(dfs(0, 'TTT'))

Solution (Python):
from datetime import datetime as dt
import itertools
N = int(input())
dp = [ [[[0 for _ in range(N + 1) ]for _ in range(5)] for _ in range(5)] for _ in range(5)]







        
MOD = 10 ** 9 + 7

dp[0][0][0][0] = 1 
A = 1
G = 2
C = 3
T = 4


for i in range(0,N):
    for c1 in range(5): 
        for c2 in range(5): 
            for c3 in range(5): 
                for c in range(1,5): 
                    if c2 == A and c1 == G and c == C:
                        continue
                    if c3 == A and c2 == G and c == C:
                        continue
                    if c3 == A and c1 == G and c == C:
                        continue
                    if c2 == G and c1 == A and c == C:
                        continue
                    if c2 == A and c1 == C and c == G:
                        continue
                    dp[c2][c1][c][i + 1] +=(dp[c3][c2][c1][i] % MOD)


ans = 0
for c1 in range(1,5):
    for c2 in range(1,5):
        for c3 in range(1,5):
            ans += dp[c3][c2][c1][N]
        

print(ans % MOD)

Solution (Python):
"""
T:0
A:1
C:2
G:3
"""

N = int(input())

dp = [[[[0]*4 for b in range(4)] for a in range(4)] for i in range(N+1)]
dp[0][0][0][0] = 1

for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                for d in range(4):
                    if b == 1 and c == 3 and d == 2: 
                        continue
                    if b == 1 and c == 2 and d == 3: 
                        continue
                    if b == 3 and c == 1 and d == 2: 
                        continue
                    if N <= 3:
                        dp[i+1][b][c][d] = 1
                        continue
                    if a == 1 and b == 3 and d == 2: 
                        continue
                    if a == 1 and c == 3 and d == 2: 
                        continue
                    dp[i+1][b][c][d] += dp[i][a][b][c]
                    dp[i+1][b][c][d] %= ((10**9)+7)

ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += dp[N][a][b][c]
            ans %= ((10**9)+7)

print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N + 1)]

    dp[0][3][3][3] = 1

    for i in range(N):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if dp[i][j][k][l] == 0:
                        continue
                    for m in range(4):
                        if k == 0 and l == 1 and m == 2:
                            continue
                        if k == 0 and l == 2 and m == 1:
                            continue
                        if k == 1 and l == 0 and m == 2:
                            continue
                        if j == 0 and k == 1 and m == 2:
                            continue
                        if j == 0 and l == 1 and m == 2:
                            continue

                        dp[i + 1][k][l][m] += dp[i][j][k][l]
                        dp[i + 1][k][l][m] %= MOD

    ans = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                ans += dp[N][j][k][l]

    print(ans % MOD)


    

    

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9+7
n = int(input())
dp = [[[ [0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
A, C, G, T = 0, 1, 2, 3
dp[0][3][3][3] = 1
for i in range(1, n+1):
    for s in range(4):
        for t in range(4):
            for u in range(4):
                for v in range(4):
                    if any( x==(t, u, v) for x in ((A,G,C), (A,C,G), (G,A,C)) ) or any( (A,G,C)==x for x in ((s,u,v), (s,t,v)) ):
                        continue
                    dp[i][t][u][v] = ( dp[i][t][u][v]+dp[i-1][s][t][u] )%MOD
print( sum( dp[n][i][j][k] for i in range(4) for j in range(4) for k in range(4) )%MOD )

Solution (Python):
n=int(input())
mod=10**9+7
if n==3:
    print(61)
    exit()
zt=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in zt:
        for k in list('AGCT'):
            tmp.append(j+k)
    zt=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
    ng.add('ACG'+i)
    ng.add('GAC'+i)
    ng.add(i+'ACG')
    ng.add(i+'GAC')
z=[]
for j in zt:
    if not j in ng:
        z.append(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)

Solution (Python):
n=int(input())
m=10**9+7

a=[1,4,16]
g=[1,4,15]
c=[1,4,14]
t=[1,4,16]

for i in range(3,n):
  a.append((a[i-1]+g[i-1]+c[i-1]+t[i-1])%m)
  t.append((a[i-1]+g[i-1]+c[i-1]+t[i-1])%m)
  g.append((a[i-1]+g[i-1]+(c[i-1]-a[i-2]+g[i-3])+t[i-1])%m)
  c.append(((a[i-1]-g[i-2])+(g[i-1]-a[i-2]-2*a[i-3])+c[i-1]+(t[i-1]-a[i-3]))%m)

n=n-1

ans=a[n]+g[n]+c[n]+t[n]
print(ans%m)

Solution (Python):
N = int(input())
MOD = 10 ** 9 + 7
A = [1] * 64
A[6] = A[9] = A[33] = 0
for _ in range(N-3):
    B = [0] * 64
    for p in range(256):
        i = p >> 2
        j = p & 63
        b = ((i == 6) or (i == 9) or (i == 33)
            or (j == 6) or (j == 9) or (j == 33)
            or (p & 207 == 9) or (p & 243 == 33))
        if not b:
            B[j] = (B[j] + A[i]) % MOD
    A[:] = B[:]
res = 0
for a in A:
    res = (res + a) % MOD
print(res)

Solution (Python):
def tetra(x):
    ret = ""
    for _ in range(3):
        ret = str(x%4) + ret
        x = (x-x%4)//4
    return ret
n = int(input())
mod = 10**9+7
if n<=2:
    print(4**n)
    exit()
DP = [[0]*64 for i in range(n+1)]
for i in range(64):
    if tetra(i) not in ["023","032","203"]:
        DP[0][i] = 1
for i in range(1,n+1):
    for j in range(64):
        tj = tetra(j)
        jprelist = [j//4+l*16 for l in range(4)]
        for jprev in jprelist:
            tjp = tetra(jprev)
            if ((tjp[1:]  in ["02","20"] or tjp[:2] == "02" or tjp == "012")
                and (tj[2] == "3")) or (tjp[1:]  == "03" and tj[2] == "2"):
                continue
            else:            
                DP[i][j] = (DP[i][j]+DP[i-1][jprev])%mod
print(sum(DP[n-3])%mod)

Solution (Python):
N=int(input())
dp=[[[[0]*5 for i in range(5)] for j in range(5)] for k in range(N+1)]
dp[0][0][0][0]=1
for n in range(N):
    for i in range(5):
        for j in range(5):
            for k in range(5):
                for l in range(1,5):
                    if i==1 and j==2 and l==3:continue
                    if i==1 and k==2 and l==3:continue
                    if j==1 and k==2 and l==3:continue
                    if j==2 and k==1 and l==3:continue
                    if j==1 and k==3 and l==2:continue
                    dp[n+1][j][k][l]+=dp[n][i][j][k]
                    dp[n+1][j][k][l]%=(10**9+7)

ans=0
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            ans+=dp[N][i][j][k]
            ans%=(10**9+7)
print(ans)

Solution (Python):
from itertools import product
n = int(input())
mod = 10 ** 9 + 7
dp = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
dp[0][0][0][0] = 1

for t in range(n):
	for i, j, k, l in product(range(5), repeat=4):
		if not (l == 0 or (j == 1) & (k == 2) & (l == 3) or (i == 1) & (j == 2) & (l == 3) or (j == 1) & (k == 3) & (l == 2)
				  or (j == 2) & (k == 1) & (l == 3) or (i == 1) & (k == 2) & (l == 3)):
			dp[t + 1][j][k][l] += dp[t][i][j][k] % mod
ans = sum(dp[-1][i][j][k] % mod for i, j, k in product(range(1, 5), repeat=3)) % mod
print(ans)

Solution (Python):
mod = 10**9+7
N = int(input())

A, G, C, T = 0, 1, 2, 3  

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]




dp[0][T][T][T] = 1
for n in range(N):
    for c0 in range(4):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    
                    if c1 == A and c2 == G and c3 == C: continue
                    if c1 == G and c2 == A and c3 == C: continue
                    if c1 == A and c2 == C and c3 == G: continue
                    if c0 == A and c1 == G and c3 == C: continue
                    if c0 == A and c2 == G and c3 == C: continue
                    
                    dp[n+1][c1][c2][c3] += dp[n][c0][c1][c2]
                    dp[n+1][c1][c2][c3] %= mod
ans = 0
for c0 in range(4):
    for c1 in range(4):
        for c2 in range(4):
            ans += dp[N][c0][c1][c2]
            ans %= mod
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
CHARS = 'ACGT'

def pos(ch):
    return CHARS.index(ch)

def ok(s):
    if 'AGC' in s:
        return False
    l = list(s)
    for i in range(len(s) - 1):
        l[i], l[i + 1] = l[i + 1], l[i]
        if 'AGC' in ''.join(l):
            return False
        l[i], l[i + 1] = l[i + 1], l[i]
    return True

n = int(input())

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
for a in CHARS:
    for b in CHARS:
        for c in CHARS:
            if ok(a + b + c):
                dp[3][pos(a)][pos(b)][pos(c)] += 1
for i in range(4, n + 1):
    for a in CHARS:
        for b in CHARS:
            for c in CHARS:
                for d in CHARS:
                    if not ok(a + b + c + d):
                        continue
                    dp[i][pos(b)][pos(c)][pos(d)] += dp[i - 1][pos(a)][pos(b)][pos(c)]
                    dp[i][pos(b)][pos(c)][pos(d)] %= MOD
ret = 0
for a in CHARS:
    for b in CHARS:
        for c in CHARS:
            ret += dp[n][pos(a)][pos(b)][pos(c)]
            ret %= MOD
print(ret)

Solution (Python):
MOD = 10 ** 9 + 7
CHARS = 'ACGT'

def pos(ch):
    return CHARS.index(ch)

def ok(s):
    if 'AGC' in s:
        return False
    l = list(s)
    for i in range(len(s) - 1):
        l[i], l[i + 1] = l[i + 1], l[i]
        if 'AGC' in ''.join(l):
            return False
        l[i], l[i + 1] = l[i + 1], l[i]
    return True

n = int(input())

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
for a in CHARS:
    for b in CHARS:
        for c in CHARS:
            if ok(a + b + c):
                dp[3][pos(a)][pos(b)][pos(c)] += 1
for i in range(4, n + 1):
    for a in CHARS:
        for b in CHARS:
            for c in CHARS:
                for d in CHARS:
                    if not ok(a + b + c + d):
                        continue
                    dp[i][pos(b)][pos(c)][pos(d)] += dp[i - 1][pos(a)][pos(b)][pos(c)]
                    dp[i][pos(b)][pos(c)][pos(d)] %= MOD
ret = 0
for a in CHARS:
    for b in CHARS:
        for c in CHARS:
            ret += dp[n][pos(a)][pos(b)][pos(c)]
            ret %= MOD
print(ret)

Solution (Python):
N=int(input())
MOD=10**9+7











ans=[1]*64
ans[6]=0
ans[9]=0
ans[33]=0
for i in range(N-3):
  val=[0]*64
  for j in range(16):
    for k in range(4):
      val[4*j+k]=(ans[j]+ans[j+16]+ans[j+32]+ans[j+48])%MOD
  val[6]=0
  val[9]=0
  val[33]=0
  val[41]=(val[41]-ans[10])%MOD
  val[45]=(val[45]-ans[11])%MOD
  val[57]=(val[57]-ans[14])%MOD
  ans=val
print(sum(ans)%MOD)

Solution (Python):
n = int(input())
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  for k in range(max(1, len(currents) - 3), len(currents)):  
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])[-4:]
  return v
 
memo = {}  
def f(index, currents):
  key = '%d:%s' % (index, currents[-4:])
  if key not in memo:
    if ng(currents):
      memo[key] = 0
    else:
      memo[key] = 1 if index == n else sum([f(index+1, currents + s) for s in seeds])
  return memo[key]
 
print(f(0, '') % int(1e9+7))

Solution (Python):
n = int(input())
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  for k in range(max(1, len(currents) - 3), len(currents)):  
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v

memo = {}  
def f(index, currents):
  key = '%d:%s' % (index, currents[-4:])
  if key not in memo:
    if ng(currents):
      memo[key] = 0
    else:
      memo[key] = 1 if index == n else sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print(f(0, '') % int(1e9+7))

Solution (Python):
n = int(input())
ans = 0
hoges = []
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  
  for k in range(max(1, len(currents) - 3), len(currents)):
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v
memo = {}
ng_memo = {} 
def f(index, currents):
  ng_key = currents[-4:]
  key = '%d:%s' % (index, currents[-4:])
  
  if ng_key in ng_memo:
    return 0
  if key in memo:
    return memo[key]
  if ng(currents):
    ng_memo[key] = True
    return 0
  if index == n:
    return 1
  memo[key] = sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print(f(0, '') % int(1e9+7))

Solution (Python):
import sys
sys.setrecursionlimit(1000)

n = int(input())
mod = 1000000007
memo = {}
def doit(n, a, b, c):
    if n == 0:
        return 1
    key = (n, a, b, c)
    if not key in memo:
        ret = (doit(n - 1, b, c, 'A') + doit(n - 1, b, c, 'T')) % mod
        if (b != 'A' or c != 'C'):
            ret = (ret + doit(n - 1, b, c, 'G')) % mod
        if (b != 'A' or c != 'G') and (b != 'G' or c != 'A') and (a != 'A' or c != 'G')  and (a != 'A' or b != 'G'):
            ret = (ret + doit(n - 1, b, c, 'C')) % mod
        memo[key] = ret
    return memo[key]
print(doit(n, '', '', ''))

Solution (Python):
import os
import re
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())


def is_ok(s):
    ok = True
    for ng in ['AGC', 'GAC', 'ACG']:
        ok &= ng not in s
    ok &= not re.match(r'A.GC', s)
    ok &= not re.match(r'AG.C', s)
    return ok



dp = [defaultdict(int) for _ in range(N)]
for c in 'AGCT':
    for d in 'AGCT':
        for e in 'AGCT':
            if is_ok(c + d + e):
                dp[2][c + d + e] = 1

for i in range(3, N):
    for k in dp[i - 1].keys():
        for c in 'AGCT':
            if is_ok(k + c):
                dp[i][k[-2:] + c] += dp[i - 1][k]
                dp[i][k[-2:] + c] %= MOD

print(sum(dp[-1].values()) % MOD)

Solution (Python):
def solve():
    MOD = 10**9+7
    N = int(input())
    
    dp = [[0 for _ in range(4)] for _ in range(N+1)]
    dp[1] = [1, 1, 1, 1]
    
    for i in range(2, N+1):
        for j in range(4):
            dp[i][j] += sum(dp[i-1])
            dp[i][j] %= MOD
        dp[i][1] -= dp[i-2][0] + dp[i-2][2]
        dp[i][2] -= dp[i-2][0]
        if 3 <= i:
            dp[i][1] -= dp[i-3][0] * 3
            dp[i][2] += dp[i-3][2]
    
    ans = sum(dp[N]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import defaultdict
n = int(input())
cs = 'ATGC'
ng = [
  'AGC',
  'GAC',
  'ACG',
  'AGGC',
  'ATGC',
  'ACGC',
  'AGAC',
  'AGTC'
]

mod = 10**9 + 7
d = defaultdict(int)
for c1 in cs:
  for c2 in cs:
    for c3 in cs:
      s = c1 + c2 + c3
      if s not in ng:
        d[s] += 1
for i in range(3, n):
  nd = defaultdict(int)
  for key in d.keys():
    for c in cs:
      cn = key[1:3] + c
      cn4 = key + c
      if cn not in ng and cn4 not in ng:
        nd[cn] = (nd[cn] + d[key]) % mod
  d = nd
print(sum([d[key] for key in d]) % mod)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

N = inp()


dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+5)]
for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i,j,k) == (0,2,1) or (i,j,k) == (0,1,2) or (i,j,k) == (2,0,1):
                continue
            dp[3][i][j][k] = 1

if N == 3:
    print(61)
    quit()
for n in range(4,N+1):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (j,k,l) == (0,2,1) or (i,k,l) == (0,2,1) or (i,j,l) == (0,2,1) or (j,k,l) == (2,0,1) or (j,k,l) == (0,1,2):
                        continue
                    dp[n][j][k][l] += dp[n-1][i][j][k]
                    dp[n][j][k][l] %= 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)