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):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n = input()
    if n == "A":
        print("T")
    elif n == "C":
        print("G")
    elif n == "G":
        print("C")
    else:
        print("A")
    return


def B():
    s = S()
    ans = 0
    n = len(s)
    for i in range(n):
        for j in range(i,n):
            f = 1
            for k in range(i,j+1):
                if s[k] not in list("AGCT"):f = 0
            if f:
                ans = max(ans,j+1-i)
    print(ans)

def C():
    n,q = LI()
    s = S()
    f = [0 for i in range(n)]
    for i in range(n-1):
        if s[i:i+2] == ["A","C"]:
            f[i+1] += 1
    for i in range(n-1):
        f[i+1] += f[i]
    f.insert(0,0)
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l])
    return


def D():
    n = I()
    dp = [[0]*64 for i in range(n+1)]
    dp[3] = [1]*64
    dp[3][6] = 0
    dp[3][9] = 0
    dp[3][18] = 0
    ng = [[0,1,2],[0,2,1],[1,0,2]]
    for i in range(3,n):
        for j in range(64):
            k = [0,0,0]
            m = j
            for o in range(3):
                k[2-o] = m%4
                m //= 4
            if k not in ng:
                for d in range(4):
                    l = k[1:]+[d]
                    m = k[:2]+[d]
                    o = [k[2]]+[k[1]]+[d]
                    o2 = [k[1]]+[d]+[k[2]]
                    o3 = [k[0]]+[k[2]]+[d]
                    if l not in ng and m != [0,1,2] and o != [0,1,2] and o2 != [0,1,2] and o3 != [0,1,2]:
                        q = 0
                        for o in range(3):
                            q += (4**o)*l[2-o]
                        dp[i+1][q] += dp[i][j]
                        dp[i+1][q] %= mod
    print(sum(dp[n])%mod)
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

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

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

for i in range(1, N + 1):
    for j in range(4):
        for k in range(4):
            for q in range(4):
                for p in range(4):
                    if i >= 3 and (k, q, p) in [(0, 1, 2), (1, 0, 2), (0, 2, 1)]:
                        continue
                    if i >= 4 and (j, q, p) == (0, 1, 2):
                        continue
                    if i >= 4 and (j, k, p) == (0, 1, 2):
                        continue
                    else:
                        dp[i][k][q][p] += dp[i - 1][j][k][q]
                        dp[i][k][q][p] %= MOD

num = 0
for j in range(4):
    for k in range(4):
        for q in range(4):
            num += dp[N][j][k][q]
            num %= MOD
print(num)

Solution (Python):
N = int(input())
D = {}
for c1 in "ACGT":
    for c2 in "ACGT":
        for c3 in "ACGT":
            D[c1+c2+c3] = [0] * 101
            D[c1+c2+c3][3] = 1
D["AGC"][3]=0
D["ACG"][3]=0
D["GAC"][3]=0

for i in range(4,101):
    for k in D:
        for c in "ACGT":
            D[k[1:]+c][i] += D[k][i-1]
            D[k[1:]+c][i] %= 10**9+7
    D["AGC"][i] = 0
    D["GAC"][i] = 0
    D["ACG"][i] = 0
    D["GGC"][i] -= D["AGG"][i-1]
    D["GGC"][i] %= 10**9+7
    D["GTC"][i] -= D["AGT"][i-1]
    D["GTC"][i] %= 10**9+7
    D["TGC"][i] -= D["ATG"][i-1]
    D["TGC"][i] %= 10**9+7

ans = 0
for k in D:
    ans += D[k][N]
    ans %= 10**9+7
print(ans)

Solution (Python):

from itertools import product
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7

N = int(input())
DP = defaultdict(int)
for a, b, c in product(range(4), repeat=3):
    DP[(a, b, c)] = 1

DP[(0, 2, 1)] = 0
DP[(0, 1, 2)] = 0
DP[(2, 0, 1)] = 0

for i in range(N-3):
    DP2 = defaultdict(int)
    for a, b, c in product(range(4), repeat=3):
        DP2[(b, c, 0)] = (DP2[(b, c, 0)] + DP[(a, b, c)])%MOD

        if (b, c) != (0, 2) and (a, c) != (0, 2) and (a, b) != (0, 2) and (b, c) != (2, 0):
            DP2[(b, c, 1)] = (DP2[(b, c, 1)] + DP[(a, b, c)])%MOD
        if (b, c) != (0, 1):
            DP2[(b, c, 2)] = (DP2[(b, c, 2)] + DP[(a, b, c)])%MOD

        DP2[(b, c, 3)] = (DP2[(b, c, 3)] + DP[(a, b, c)])%MOD
    DP = DP2
print(sum(DP.values())%MOD)

Solution (Python):

from itertools import product
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7

N = int(input())
DP = defaultdict(int)
for a, b, c in product(range(4), repeat=3):
    DP[(a, b, c)] = 1

DP[(0, 2, 1)] = 0
DP[(0, 1, 2)] = 0
DP[(2, 0, 1)] = 0

for i in range(N-3):
    DP2 = defaultdict(int)
    for a, b, c in product(range(4), repeat=3):
        DP2[(b, c, 0)] = (DP2[(b, c, 0)] + DP[(a, b, c)])%MOD

        if (b, c) != (0, 2) and (a, c) != (0, 2) and (a, b) != (0, 2) and (b, c) != (2, 0):
            DP2[(b, c, 1)] = (DP2[(b, c, 1)] + DP[(a, b, c)])%MOD
        if (b, c) != (0, 1):
            DP2[(b, c, 2)] = (DP2[(b, c, 2)] + DP[(a, b, c)])%MOD

        DP2[(b, c, 3)] = (DP2[(b, c, 3)] + DP[(a, b, c)])%MOD
    DP = DP2
print(sum(DP.values())%MOD)

Solution (Python):
import numpy as np
N = int(input())
M = 10**9 + 7

P = np.empty((4,4,4),dtype=np.int64)
Q = np.ones((4,4,4),dtype=np.int64)
Q[0,2,1] = Q[2,0,1] = Q[0,1,2] = 0
for n in range(3,N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in [(0,2,1), (2,0,1), (0,1,2)]:
                    P[i,j,k] = 0
                elif (j,k) == (2,1) or (i,k) == (2,1):
                    P[i,j,k] = Q[1:,i,j].sum() % M 
                else:
                    P[i,j,k] = Q[:,i,j].sum() % M
    (P, Q) = (Q, P)

print(Q.sum() % M)

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

dp = [
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ],
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ],
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ],
    [
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]],
        [[1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)], [1 if i==0 else 0 for i in range(N-2)]]
    ]
]

dp[0][1][2][0] = 0
dp[0][2][1][0] = 0
dp[1][0][2][0] = 0

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    dp[j][k][l][m+1] %= M
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]
            total %= M
print(total)

Solution (Python):
N = int(input().strip())
M = pow(10, 9) + 7
a = 1
g = 1
ag = 0
agg = 0
agt = 0
atg = 0
ac = 0
at = 0
aa = 0
ga = 0

al = 4
nal = 0

for i in range(N-1):
    nal = (al * 4) % M
    nal = (nal + M - (ag + ac + ga + agg + agt + atg) ) % M

    agg = ag
    agt = ag
    atg = at
    ag = a
    aa = a
    at = a
    nac = (a + M- ga) % M
    ga = g
    a = al
    g = (al + M - ac) % M
    ac = nac
    al = nal
print(al)

Solution (Python):

import itertools
import sys
import math
from functools import lru_cache


n = int(input())
if n == 3:
    print('61')
    quit()

divide = 1000000007

agct = ['A', 'G', 'C', 'T']

out = set()
for c in agct:
    out.add('AGC' + c)
    out.add(c+'AGC')
    out.add( 'A' + c + 'GC')
    out.add('AG' + c + 'C')
    out.add('GAC' + c)
    out.add(c+'GAC')
    out.add('ACG' + c)
    out.add(c+'ACG')


def isok(str):
    if str[-4:] in out:
        return False
    return True



@lru_cache(maxsize=1000000)
def saiki(n,str):
    if n == 4:
        if isok(str):
            return 1
        return 0
    ret = 0
    if isok(str)==False:
        return 0
    for c in agct:
        next = c+str
        next = next[0:4]
        ret += saiki(n-1,next)
    return ret%divide

strlist = list(itertools.product(agct, repeat=4))

rr = 0
for strs in strlist:
    rr += saiki(n,''.join(strs))
print(rr%divide)

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

s = ['A', 'C', 'G', 'T']
invs = ['AGC', 'ACG', 'GAC']

d = {}
for c1 in s:
    for c2 in s:
        for c3 in s:
            d[c1+c2+c3] = 1 if c1+c2+c3 not in invs else 0

dn = {}
for _ in range(N - 3):
    for c1 in s:
        for c2 in s:
            for c3 in s:
                cnt = 0
                for c0 in s:
                    if c0+c2+c3!='AGC' and c0+c1+c3!='AGC':
                        cnt += d[c0+c1+c2]
                dn[c1+c2+c3] = cnt%1000000007 if c1+c2+c3 not in invs else 0
    dn, d = d, dn

print(sum(d.values())%1000000007)

Solution (Python):
import sys
import numpy as np
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n = int(input())
dp = [[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
dp[0][0][0][0] = 1
mod = 10**9+7
en = ["A","G","C","T"]
def han(mozi):
        if mozi.find("AGC") != -1:
                return 1
        mozi2 = mozi[1] + mozi[0] + mozi[2:]
        if mozi2.find("AGC") != -1:
                return 1    
        mozi3 = mozi[0] + mozi[2] + mozi[1] + mozi[3]
        if mozi3.find("AGC") != -1:
                return 1    
        mozi4 = mozi[0] + mozi[1] + mozi[3] + mozi[2]
        if mozi4.find("AGC") != -1:
                return 1             
        return 0
for i in range(n):
        for j in range(4):
                for k in range(4):
                        for l in range(4):
                                for o in range(4):
                                        if i== 2:
                                                if o == 0 and j ==1 and k == 2:
                                                        continue
                                                if o == 0 and j ==2 and k == 1:
                                                        continue
                                                if o == 1 and j ==0 and k == 2:
                                                        continue
                                                dp[i+1][o][j][k] += dp[i][j][k][l]
                                        elif i < 2:
                                                dp[i+1][o][j][k] += dp[i][j][k][l]
                                        else:
                                                mozi = en[o] + en[j] + en[k]+ en[l]
                                                if han(mozi):
                                                        continue
                                                dp[i+1][o][j][k] += dp[i][j][k][l]
                                                dp[i+1][o][j][k] %= mod
print(np.sum(np.array(dp[n]))%mod)

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

mod = 10**9 + 7

dp = [[0] * (4**3) for _ in range(n+1)]

for w in range(4**3):
    if (w // 16) % 4 == 0 and (w // 4) % 4 == 2 and w % 4 == 3:
        continue
    if (w // 16) % 4 == 0 and (w // 4) % 4 == 3 and w % 4 == 2:
        continue
    if (w // 16) % 4 == 2 and (w // 4) % 4 == 0 and w % 4 == 3:
        continue
    dp[3][w] = 1

for i in range(3, n):
    for w in range(4**3):
        for nw in range(4):
            if (w // 4) % 4 == 0 and w % 4 == 2 and nw == 3:
                continue
            if (w // 4) % 4 == 0 and w % 4 == 3 and nw == 2:
                continue
            if (w // 4) % 4 == 2 and w % 4 == 0 and nw == 3:
                continue
            if (w // 16) % 4 == 0 and (w // 4) % 4 == 2 and nw == 3:
                continue
            if (w // 16) % 4 == 0 and w % 4 == 2 and nw % 4 == 3:
                continue
            dp[i+1][(((w // 4) % 4) * 16 + (w % 4) * 4) + nw] += dp[i][w]
            dp[i+1][(((w // 4) % 4) * 16 + (w % 4) * 4) + nw] %= mod

ans = 0
for w in range(4**3):
    ans += dp[n][w]
    ans %= mod

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m
    
    def add(self, a, b):
        return (a + b ) % self.m

    def sub(self, a, b):
        return (a - b) % self.m
    
    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, self.pow(b, self.m-2))

    def pow(self, x, y):
        if y == 0: 
            return 1
        elif y == 1: 
            return x % self.m
        elif y % 2 == 0: 
            return self.pow(x, y//2)**2 % self.m
        else: 
            return self.pow(x, y//2)**2 * x % self.m


@mt
def slv(N):
    if N==3:
        return 61

    m = Mod(10**9+7)
    dp = {}
    iv = [
        'agc',
        'acg',
        'gac',
        'aggc'
        'acgc',
        'atgc',
        'agac',
        'aggc',
        'agtc',
    ]
    for s in product('agct', repeat=4):
        s = ''.join(s)
        if not any(map(lambda x: x in s, iv)):
            dp[s] = 1

    for _ in range(N-4):
        dp_ = Counter()
        for k, v in dp.items():
            for c in 'agct':
                s = k + c
                if not any(map(lambda x: x in s, iv)):
                    dp_[s[1:]] = m.add(v, dp_[s[1:]])
        dp = dp_
    
    ans = 0
    for k, v in dp.items():
        ans = m.add(ans, v)


    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product

MOD = 10**9 + 7
N = int(input())
assert 3 <= N <= 100

char_to_idx = {"A": 0, "C": 1, "G": 2, "T": 3}



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


invalid_seqs = set(["AGC", "ACG", "GAC"])
for chars in product(char_to_idx.keys(), repeat=3):
    string = "".join(chars)
    if string not in invalid_seqs:
        i1, i2, i3 = [char_to_idx[char] for char in string]
        dp[2][i1][i2][i3] = 1

invalied_indices = set()
for chars in product(char_to_idx.keys(), repeat=4):
    string = "".join(chars)
    if string[:3] == "AGC" or string[1:] == "AGC":
        invalied_indices.add(tuple(char_to_idx[char] for char in string))
        continue
    for i in range(3):
        new_string = list(string)
        new_string[i], new_string[i + 1] = string[i + 1], string[i]
        new_string = "".join(new_string)
        if new_string[:3] == "AGC" or new_string[1:] == "AGC":
            invalied_indices.add(tuple(char_to_idx[char] for char in string))
            break


for i in range(3, N):
    for i0 in range(4):
        for i1 in range(4):
            for i2 in range(4):
                for i3 in range(4):
                    if (i0, i1, i2, i3) not in invalied_indices:
                        dp[i][i1][i2][i3] += dp[i - 1][i0][i1][i2]
                        dp[i][i1][i2][i3] %= MOD

num_strings = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            num_strings += dp[-1][i][j][k]
            num_strings %= MOD
print(num_strings)

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


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

for i in range(4):
    for j in range(4):
        for k in range(4):
            if (i == 0 and j == 1 and k == 2) or \
               (i == 0 and j == 2 and k == 1) or \
               (i == 1 and j == 0 and k == 2):
                   continue

            dp[3][i][j][k] += 1




restriction = "AGCT" 

for i in range(4, N+1):

    for i2 in range(4):
        for j in range(4):
            for k in range(4): 
                for p in range(4):

                    
                    if   (j == 0 and k ==  1 and p == 2) or \
                         (j == 0 and k ==  2 and p == 1) or \
                         (j == 1 and k ==  0 and p == 2) : 
                             continue

                    if   (i2 == 0 and k == 1 and p == 2) or \
                         (i2 == 0 and j == 1 and p == 2) :
                             continue

                    dp[i][j][k][p] = (dp[i][j][k][p] + dp[i-1][i2][j][k]) % mod


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

Solution (Python):
N = int(input())
p = 10 ** 9 + 7
DP = [[0 for j in range(16)] for i in range(N)]
for i in range(16):
  DP[1][i] = 1
for i in range(2, N):
  DP[i][0] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][8] + DP[i - 1][12]) % p 
  DP[i][1] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][12]) % p 
  DP[i][2] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][8] + DP[i - 1][12]) % p 
  DP[i][3] = (DP[i - 1][0] + DP[i - 1][4] + DP[i - 1][8] + DP[i - 1][12]) % p 
  DP[i][4] = (DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p 
  DP[i][5] = (DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p 
  DP[i][6] = (DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p 
  DP[i][7] = (DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]) % p 
  DP[i][8] = (DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]) % p 
  DP[i][9] = (DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14] - DP[i - 2][2] - DP[i - 2][3]) % p 
  DP[i][10] = (DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]) % p 
  DP[i][11] = (DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]) % p 
  DP[i][12] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]) % p 
  DP[i][13] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15] - DP[i - 2][2]) % p 
  DP[i][14] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]) % p 
  DP[i][15] = (DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]) % p 
print(sum(DP[N - 1]) % p)

Solution (Python):
MOD = pow(10,9) + 7

chars = ["A","C","G","T"]
dict = {
    "A":0,
    "C":1,
    "G":2,
    "T":3
}
invDict = ["A","C","G","T"]
illegalFours = []
for c in chars:
    illegalFours.append("AGC"+c)
    illegalFours.append(c+"AGC")
    illegalFours.append("ACG"+c)
    illegalFours.append(c+"ACG")
    illegalFours.append("GAC"+c)
    illegalFours.append(c+"GAC")
    illegalFours.append("AG"+c+"C")
    illegalFours.append("A"+c+"GC")
illegalFours = list(set(illegalFours))

def isLegal(value):
    f1,q = divmod(value,64)
    f2,q = divmod(q,16)
    f3,q = divmod(q,4)
    f4 = q
    
    string = invDict[f1] + invDict[f2] + invDict[f3] + invDict[f4]
    return(string not in illegalFours)
valueIsLegal = [isLegal(i) for i in range(4**4)]


def calcNextValue(value,x):
    return((value*4 + x)%256)
    
def solve(x):
    if x==3:
        return(61)
    dp = [[0 for _ in range(x+1)] for _ in range(256)]
    for value in range(256):
        if valueIsLegal[value]:
            dp[value][4] = 1
        else:
            dp[value][4] = 0
    for k in range(4,x):
        for v in range(256):
            for i in range(4):
                w = calcNextValue(v,i)
                if valueIsLegal[w]:
                    dp[w][k+1] += dp[v][k]
                    dp[w][k+1] %= MOD
    ans = 0
    for v in range(256):
        ans += dp[v][x]
        ans %= MOD
    return(ans)

N = int(input())
print(solve(N))

Solution (Python):
print([0, 0, 0, 61, 230, 865, 3247, 12185, 45719, 171531, 643550, 2414454, 9058467, 33985227, 127504505, 478366600, 794717734, 733354121, 261943303, 776803305, 580025381, 51688048, 44657419, 737209731, 604119499, 159693437, 858533109, 639056669, 549054109, 996291083, 531294469, 23314687, 783022045, 855462856, 649970414, 68697295, 409213624, 604356692, 88638656, 978442997, 534833116, 763737161, 785892908, 123883652, 639213333, 181836645, 998121103, 124885216, 501575626, 39816123, 113468411, 799008836, 775465589, 256852905, 664630886, 971550783, 751629411, 51018086, 702530485, 725438992, 696683714, 792638194, 221791721, 149602322, 414054379, 986519078, 981760191, 305799096, 515140586, 406959393, 975058685, 245601370, 324759692, 673385295, 191483611, 570246669, 427196161, 781042769, 569725155, 842176273, 25328739, 847501730, 206282374, 353770801, 323137024, 371653459, 940737264, 123820509, 915711339, 847205021, 252858375, 718889563, 866398347, 738390145, 133009077, 333099663, 170591295, 329869205, 616680192, 597534442, 388130742][int(input())])

Solution (Python):
from collections import defaultdict
mod = 10**9 + 7

n = int(input())
cnt = {}
cnt[3] = defaultdict(lambda: 0)

def ok_quad(s):
  if 'AGC' not in s and 'AGC' not in s[1]+s[0]+s[2]+s[3] and 'AGC' not in s[0]+s[2]+s[1]+s[3] and 'AGC' not in s[0]+s[1]+s[3]+s[2]:
    return True
  else:
    return False
l = list('AGCT')
i = 3
for c1 in l:
  for c2 in l:
    for c3 in l:
      s = c1 + c2 + c3
      if s != 'AGC' and s != 'GAC' and s != 'ACG':
        cnt[i][s] += 1

for nn in range(4,n+1):
  cnt[nn] = defaultdict(lambda: 0)
  for ss in cnt[nn-1].keys():
    for c in l:
      sq = ss + c
      if ok_quad(sq):
        st = sq[1:]
        cnt[nn][st] += cnt[nn-1][ss] % mod

sm = sum(cnt[n].values()) % mod
print(sm)

Solution (Python):
from itertools import product
MOD = 10 ** 9 + 7

N = int(input())
dp = {}
for s in product('ATCG', repeat=3):
  dp[s] = int(s not in [('A','G','C'), ('G','A','C'), ('A','C','G'),])

for _ in range(3, N):
  ndp = {}
  for s in product('ATCG', repeat=3):
    if s[2] in ['A', 'T']:
      ndp[s] = sum([
        v for k,v in dp.items()
        if k[1] == s[0] and k[2] == s[1]
      ]) % MOD
    elif s[2] == 'G':
      ndp[s] = sum([
        v for k,v in dp.items()
        if (
          k[1] == s[0] and k[2] == s[1] and
          (k[1] != 'A' or k[2] != 'C')
        )
      ]) % MOD
    else:
      ndp[s] = sum([
        v for k,v in dp.items()
        if k[1] == s[0] and k[2] == s[1] and not (
          (k[1] == 'A' and k[2] == 'G') or
          (k[0] == 'A' and k[2] == 'G') or
          (k[1] == 'G' and k[2] == 'A') or
          (k[0] == 'A' and k[1] == 'G')
        )
      ]) % MOD
  dp = ndp
print(sum(dp.values()) % MOD)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()

D = ['AAGC', 'GAGC', 'CAGC', 'TAGC', 'AGGC', 'ACGC', 'ATGC', 'AGCA', 'AGCG', 'AGCC', 'AGCT', 'AGAC', 'AGGC', 'AGTC']
D += ['ACGA', 'ACGG', 'ACGC', 'ACGT', 'AACG', 'GACG', 'CACG', 'TACG']
D += ['GACA', 'GACG', 'GACC', 'GACT', 'AGAC', 'GGAC', 'CGAC', 'TGAC']
m = {}
for a, b, c in it.product('AGCT', repeat = 3):
    S = a + b + c
    if not S in ['AGC', 'ACG', 'GAC']:
        m[S] = 1
cnt = 0
for _ in range(3, N):
    m2 = {}
    for key in m:
        for c in 'AGCT':
            S = key + c
            if not S in D:
                cnt += 1
                if S[1:] in m2:
                    m2[S[1:]] += m[key]
                    m2[S[1:]] %= MOD
                else:
                    m2[S[1:]] = m[key]
    m = m2
ans = 0
for key in m:
    ans += m[key]
    ans %= MOD
print ans

Solution (Python):
sets=["A","T","G","C"]
outs = ["AGC", "ACG","GAC"]
outs2 = ["ATGC","AGGC","AGTC"]
N = int(input())

befs = {}
afts = {}
for s in sets:
	for t in sets:
		for  u in sets:
			v = s+t+u
			if not v in outs:
				afts[s+t+u] = 1
				befs[s+t+u] = 1

for i in range(4,N+1):
	for a in afts.keys():
		afts[a]=0
	for s in sets:
		for b in befs.keys():
			t = s+b
			if not t[:3] in outs and not t in outs2:
				afts[t[:3]] += befs[b]
	
	for a in afts.keys():
		befs[a] = afts[a] %1000000007

ans = 0
for a in afts.keys():
	ans += afts[a]
ans %= 1000000007
print(ans)

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


answer = [1]*64;
answer[9]=0; 
answer[6]=0; 
answer[33]=0;

if(N>3):
    for i in range(3,N):
        new_answer = [0]*64;
        for j in range(64):
            if j==25 or j==37 or j==41 or j==45 or j==57:
                
                for k in range(1,4):
                    new_answer[j] += answer[j//4 + 16*k];
            else:
                for k in range(4):
                    new_answer[j] += answer[j//4 + 16*k];
            new_answer[9]=0;
            new_answer[6]=0;
            new_answer[33]=0;
        for j in range(64):
            answer[j]=new_answer[j];

total = 0;

for j in range(64):
    total += answer[j];

print(total % 1000000007);

Solution (Python):
N = int(input())
if N==3:
    print(61)
    exit()

MOD = 10**9+7
dp = [[0]*64 for i in range(N-2)]

A,C,G,T = 0,1,2,3
for i in range(4):
    for j in range(4):
        for k in range(4):
            if i==A and j==G and k==C: continue
            if i==A and j==C and k==G: continue
            if i==G and j==A and k==C: continue
            dp[0][i*16 + j*4+ k] = 1

for i in range(N-3):
    for j in range(64):
        a,b = divmod(j,16)
        b,c = divmod(b,4)
        for d in range(4):
            if b==A and c==G and d==C: continue
            if b==A and c==C and d==G: continue
            if b==G and c==A and d==C: continue
            if a==A and b==G and d==C: continue
            if a==A and c==G and d==C: continue
            dp[i+1][b*16+c*4+d] += dp[i][j]
            dp[i+1][b*16+c*4+d] %= MOD
print(sum(dp[-1]) % MOD)

Solution (Python):
def no(x, y, z, k):
    return ([y, z, k] == [1, 2, 3]) or ([y, z, k] == [2, 1, 3]) or ([y, z, k] == [1, 3, 2]) or ([x, z, k] == [1, 2, 3]) or ([x, y, k] == [1, 2, 3])

MOD = 10**9 + 7
n = int(input())
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
dp[0][0][0][0] = 1
for i in range(n):
    for x in range(4):
        for y in range(4):
            for z in range(4):
                for k in range(4):
                    if not no(x, y, z, k):
                        dp[i + 1][y][z][k] += dp[i][x][y][z]
                        dp[i + 1][y][z][k] %= MOD
ans = 0
for x in range(4):
    for y in range(4):
        for z in range(4):
            ans += dp[n][x][y][z]
            ans %= MOD
print(ans)