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):
def ok(last4):
    ret = True
    if last4 in ["ATGC","AGGC","AGTC"]:
        ret = False
    elif True in [s in last4 for s in ["AGC","ACG","GAC"]]:
        ret = False
    return ret
N = int(input())
mod = 10**9+7
memo = [{} for i in range(N+1)]

def dfs(current, last3):
    if last3 in memo[current]:
        return memo[current][last3]
    if current == N:
        return 1
    ret = 0
    for c in "ATGC":
        if ok(last3+c):
            ret += dfs(current+1, last3[1:]+c)
            ret %= mod
    memo[current][last3] = ret
    return ret

print(dfs(0, "TTT"))

Solution (Python):
I=1000000007
n=int(input())
s=["A","C","G","T"]
List=["AGCA","AGCC","AGCG","AGCT","ACGA","ACGC","ACGG","ACGT","GACA","GACC","GACG","GACT","AAGC","CAGC","GAGC","TAGC","CACG","AACG","TACG","AGAC","CGAC","GGAC","TGAC","ATGC","AGGC","AGTC"]
dp=[[0]*(64) for i in range(n-2)]
for i in range(64):
    if i not in {6,9,33}:
        dp[0][i]=1
if n==3:
    print(61)
else:
    for i in range(n-3):
        for a in range(len(s)):
            for b in range(len(s)):
                for c in range(len(s)):
                    for d in range(len(s)):
                        if s[a]+s[b]+s[c]+s[d] not in List:
                            dp[i+1][b*16+c*4+d]=(dp[i+1][b*16+c*4+d]+dp[i][a*16+b*4+c])%I

    print(sum(dp[-1])%I)

Solution (Python):
mod=10**9+7
n=int(input())
A,T,G,C=[0]*(n+1),[0]*(n+1),[0]*(n+1),[0]*(n+1)
A[1],A[2],A[3]=1,4,16
T[1],T[2],T[3]=1,4,16
C[1],C[2],C[3]=1,4,14
G[1],G[2],G[3]=1,4,15
S=[0]*(n+1)
S[1],S[2],S[3]=4,16,61
for i in range(4,n+1):
    A[i],T[i]=S[i-1],S[i-1]
    C[i]=S[i-1]-(A[i-2]+G[i-2]+A[i-3]*3)
    G[i]=S[i-1]-(A[i-2]-G[i-3])
    S[i]=(A[i]+T[i]+C[i]+G[i])%mod
print(S[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import product

def cnt(N):
    ret = 0
    for s in product('ACGT', repeat=N):
        s = ''.join(s)
        if 'AGC' in s or 'GAC' in s or 'ACG' in s:
            continue
        if 'AGGC' in s or 'ATGC' in s or 'AGTC' in s:
            continue
        ret += 1
    return ret

def main():
    N = II()
    ans = 0
    dp = {'':1, 'A':0, 'G':0, 'GA':0, 'AC':0, 'AT':0, 'AG':0,
        'ATG':0, 'AGT':0, 'AGG':0}
    for _ in range(N):
        tmp = {}
        tmp[''] = dp[''] * 2 + dp['G'] * 2 + \
            dp['AC'] * 2 + dp['AT'] * 2 + \
            dp['ATG'] * 1 + dp['AGT'] * 1 + dp['AGG'] * 1
        tmp['A'] = dp[''] + dp['A'] + dp['GA'] + dp['AC'] + dp['AT'] + dp['AGT']
        tmp['G'] = dp[''] + dp['G'] + dp['AGG'] + dp['ATG'] + dp['AGT']
        tmp['GA'] = dp['G'] + dp['AG'] + dp['ATG'] + dp['AGG']
        tmp['AC'] = dp['A']
        tmp['AT'] = dp['A'] + dp['GA']
        tmp['AG'] = dp['A'] + dp['GA']
        tmp['ATG'] = dp['AT']
        tmp['AGT'] = dp['AG']
        tmp['AGG'] = dp['AG']
        dp = tmp
    ans = sum(v for v in dp.values())

    return ans % MOD

print(main())

Solution (Python):
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))

Solution (Python):
N=int(input())
MOD=10**9+7
a=[[0 for i in range(64)] for j in range(101)]
a[3]=[1 for i in range(64)]
a[3][6],a[3][9],a[3][18]=0,0,0
for i in range(4,N+1):
  a[i][0]=(a[i-1][0]+a[i-1][16]+a[i-1][32]+a[i-1][48])%MOD
  a[i][1]=a[i][0]
  a[i][2]=a[i][0]
  a[i][3]=a[i][0]
  a[i][4]=(a[i-1][1]+a[i-1][17]+a[i-1][33]+a[i-1][49])%MOD
  a[i][5]=a[i][4]
  a[i][6]=0
  a[i][7]=a[i][4]
  a[i][8]=(a[i-1][2]+a[i-1][18]+a[i-1][34]+a[i-1][50])%MOD
  a[i][9]=0
  a[i][10]=a[i][8]
  a[i][11]=a[i][8]
  a[i][12]=(a[i-1][3]+a[i-1][19]+a[i-1][35]+a[i-1][51])%MOD
  a[i][13]=a[i][12]
  a[i][14]=a[i][12]
  a[i][15]=a[i][12]
  a[i][16]=(a[i-1][4]+a[i-1][20]+a[i-1][36]+a[i-1][52])%MOD
  a[i][17]=a[i][16]
  a[i][18]=0
  a[i][19]=a[i][16]
  a[i][20]=(a[i-1][5]+a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][21]=a[i][20]
  a[i][22]=(a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][23]=a[i][20]
  a[i][24]=(a[i-1][6]+a[i-1][22]+a[i-1][38]+a[i-1][54])%MOD
  a[i][25]=a[i][24]
  a[i][26]=a[i][24]
  a[i][27]=a[i][24]
  a[i][28]=(a[i-1][7]+a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][29]=a[i][28]
  a[i][30]=(a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][31]=a[i][28]
  a[i][32]=(a[i-1][8]+a[i-1][24]+a[i-1][40]+a[i-1][56])%MOD
  a[i][33]=a[i][32]
  a[i][34]=a[i][32]
  a[i][35]=a[i][32]
  a[i][36]=(a[i-1][9]+a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][37]=a[i][36]
  a[i][38]=(a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][39]=a[i][36]
  a[i][40]=(a[i-1][10]+a[i-1][26]+a[i-1][42]+a[i-1][58])%MOD
  a[i][41]=a[i][40]
  a[i][42]=a[i][40]
  a[i][43]=a[i][40]
  a[i][44]=(a[i-1][11]+a[i-1][27]+a[i-1][43]+a[i-1][59])%MOD
  a[i][45]=a[i][44]
  a[i][46]=a[i][44]
  a[i][47]=a[i][44]
  a[i][48]=(a[i-1][12]+a[i-1][28]+a[i-1][44]+a[i-1][60])%MOD
  a[i][49]=a[i][48]
  a[i][50]=a[i][48]
  a[i][51]=a[i][48]
  a[i][52]=(a[i-1][13]+a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][53]=a[i][52]
  a[i][54]=(a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][55]=a[i][52]
  a[i][56]=(a[i-1][14]+a[i-1][30]+a[i-1][46]+a[i-1][62])%MOD
  a[i][57]=a[i][56]
  a[i][58]=a[i][56]
  a[i][59]=a[i][56]
  a[i][60]=(a[i-1][15]+a[i-1][31]+a[i-1][47]+a[i-1][63])%MOD
  a[i][61]=a[i][60]
  a[i][62]=a[i][60]
  a[i][63]=a[i][60]
print(sum(a[N])%MOD)

Solution (Python):


import itertools
import collections
import bisect

dp = [{} for _ in range(101)]

def is_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') > 0:
            return False
    return True


def solve(rest, lastt):
    if rest == 0:
        
        return 1
    if lastt in dp[rest]:
        return dp[rest][lastt]

    val = 0
    for c in 'AGCT':
        if is_ok(lastt + c):
            val += solve(rest - 1, lastt[1:] + c)
    dp[rest][lastt] = val
    return dp[rest][lastt]


def main():
    N = int(input())
    MOD = 10 ** 9 + 7
    print(solve(N, 'ZZZ') % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
import functools


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


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


@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    return ret


print(dfs(0, 'TTT'))

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i 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):
	if last3 in memo[cur]:
		return memo[cur][last3]
	if cur == N:
		return 1
	ret = 0
	for c in 'ACGT':
		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 bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))



N = 0


def set_inputs():
    global N
    N = get_int()
    return


DIVISOR = 1000000007


def main():
    setrecursionlimit(100000)
    set_inputs()

    
    safe = [0] * (N+1)
    a = [0] * (N+1)
    g = [0] * (N+1)
    ac = [0] * (N+1)
    ag = [0] * (N+1)
    at = [0] * (N+1)
    ga = [0] * (N+1)
    agg = [0] * (N+1)
    agt = [0] * (N+1)
    atg = [0] * (N+1)

    safe[0] = 1
    for i in range(1, N+1):
        s = safe[i-1] * 2
        s += g[i-1] * 2
        s += ac[i-1] * 2
        s += at[i-1] * 2
        s += agg[i-1]
        s += agt[i-1]
        s += atg[i-1]
        safe[i] = s % DIVISOR

        a_ = safe[i-1]
        a_ += a[i-1]
        a_ += ac[i-1]
        a_ += at[i-1]
        a_ += ga[i-1]
        a_ += agt[i-1]
        a[i] = a_ % DIVISOR

        g_ = safe[i-1]
        g_ += g[i-1]
        g_ += agg[i-1]
        g_ += agt[i-1]
        g_ += atg[i-1]
        g[i] = g_ % DIVISOR

        ac[i] = a[i-1]
        ag[i] = ( a[i-1] + ga[i-1]) % DIVISOR
        at[i] = ( a[i-1] + ga[i-1]) % DIVISOR
        ga[i] = ( g[i-1] + ag[i-1] + agg[i-1] + atg[i-1]) % DIVISOR
        agg[i] = ag[i-1]
        agt[i] = ag[i-1]
        atg[i] = at[i-1]

        
    print((safe[N] + a[N] + g[N] + ac[N] + ag[N] + at[N] + ga[N] + agg[N] + agt[N] + atg[N]) % DIVISOR)
    return


if __name__ == '__main__':
    main()

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

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

dame = ['AGC','GAC','ACG']

o = 'AGC'

for ap in x:
    dame.append(o[0]+ap+o[1:])
    dame.append(o[:-1]+ap+o[-1])


l = list(itertools.product(x,x,x))

ll = len(l)
D = 10**9+7
for i in range(ll):
    l[i] = ''+l[i][0]+l[i][1]+l[i][2]
cnt = [1]*len(l)

for i in range(3,n):
    new_cnt = [0]*ll
    for j in range(ll):
        for ap in x:
            s = l[j]+ap
            if s in dame or s[1:] in dame or s[:-1] in dame:
                continue
            else:
                new_cnt[l.index(s[1:])]+=cnt[j]
    cnt = new_cnt
    for j in range(ll):
        cnt[j] %= D
res = 0
for i in range(ll):
    if l[i] not in dame:
        res += cnt[i] 
print(res%D)

Solution (Python):

import sys
input = sys.stdin.readline

import numpy as np

mod = 10 ** 9 + 7

def question():
    n = int(input())

    a = [0] * (n+1)
    a[1] = 1
    a[2] = 4
    a[3] = 16

    t = [0] * (n+1)
    t[1] = 1
    t[2] = 4
    t[3] = 16

    c = [0] * (n+1)
    c[1] = 1
    c[2] = 4
    c[3] = 14

    g = [0] * (n+1)
    g[1] = 1
    g[2] = 4
    g[3] = 15

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

        
        
        
        

    print((a[n]+t[n]+c[n]+g[n]) % mod)


question()

Solution (Python):
n=int(input())
x=10**9+7
sa=[1,4,16]
sg=[1,4,15]
sc=[1,4,14]
st=[1,4,16]
for i in range(3,n):
    sa.append(sa[i-1]+sg[i-1]+sc[i-1]+st[i-1])
    sg.append(sa[i-1]+sg[i-1]+(sc[i-1]-sa[i-2]+sg[i-3])+st[i-1])
    sc.append((sa[i-1]-sg[i-2])+(sg[i-1]-sa[i-2]-sa[i-3]-sa[i-3])+(sc[i-1])+(st[i-1]-sa[i-3]))
    st.append(sa[i-1]+sg[i-1]+sc[i-1]+st[i-1])
n=n-1
print((sa[n]+sg[n]+sc[n]+st[n])%x)

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

dp_A = [1] + [0] * (N + 5)
dp_G = [1] + [0] * (N + 5)
dp_C = [1] + [0] * (N + 5)
dp_T = [1] + [0] * (N + 5)
dp_AG = [0] * (N + 5)
dp_AC = [0] * (N + 5)
dp_GA = [0] * (N + 5)
dp_AGA = [0] * (N + 5)
dp_AGG = [0] * (N + 5)
dp_AGT = [0] * (N + 5)
dp_AAG = [0] * (N + 5)
dp_AGG = [0] * (N + 5)
dp_ATG = [0] * (N + 5)
dp_ok = [4] + [0] * (N + 5)

for i in range(1, N):
    dp_A[i] = dp_ok[i - 1]
    dp_C[i] = dp_ok[i - 1] - dp_AG[i - 1] - dp_GA[i - 1] - dp_AGG[
        i - 1] - dp_AGT[i - 1] - dp_ATG[i - 1]
    dp_C[i] %= mod
    dp_G[i] = dp_ok[i - 1] - dp_AC[i - 1]
    dp_G[i] %= mod
    dp_T[i] = dp_ok[i - 1]
    dp_T[i] %= mod
    dp_AG[i] = dp_A[i - 1]
    dp_AG[i] %= mod
    dp_AC[i] = dp_A[i - 1] - dp_GA[i - 1]
    dp_AC[i] %= mod
    dp_GA[i] = dp_G[i - 1]
    dp_GA[i] %= mod
    dp_AGG[i] = dp_AG[i - 1]
    dp_AGG[i] %= mod
    dp_AGT[i] = dp_AG[i - 1]
    dp_AGT[i] %= mod
    dp_ATG[i] = dp_A[i - 2]
    dp_ATG[i] %= mod
    dp_ok[i] = dp_A[i] + dp_C[i] + dp_G[i] + dp_T[i]
    dp_ok[i] %= mod
print(dp_ok[N - 1])

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
                s = s[1:]
                if s in dp:
                    dp_[s] = m.add(v, dp_[s])
        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):

N = int(input())

res_dict = dict()
for i0 in "ACGT":
    for i1 in "ACGT":
        for i2 in "ACGT":
            s = i0+i1+i2
            if s in ["AGC", "ACG", "GAC"]:
                res_dict[s] = [0, 0, 0, 0] + [0]*(N-3)
            else:
                res_dict[s] = [0, 0, 0, 1] + [0]*(N-3)

for i in range(3, N):
    for k in res_dict.keys():
        for add in "ACGT":
            s = k + add
            if k[1:] + add in ["AGC", "ACG", "GAC"] or k[:2] + add == "AGC" or k[0] + k[2] + add == "AGC":
                pass
            else:
                res_dict[s[1:]][i+1] += res_dict[k][i]
                
print(sum([res_dict[s][N] for s in res_dict.keys()]) % (10**9+7))

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

mp=['A','C','G','T']
out=['AGC','ACG','GAC']

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

for k in range(3,N):
    for x in range(4):
        for y in range(4):
            for i in range(4):
                for j in range(4):
                    if mp[i]+mp[y]+mp[x] in out:continue
                    if mp[j]+mp[y]+mp[x] == 'AGC': continue
                    if mp[j]+mp[i]+mp[x] == 'AGC': continue
                    
                    dp[k][x][y][i] = (dp[k][x][y][i] + dp[k-1][y][i][j])%MOD


res=0
for d in dp[-1]:
    for row in d:
        res=(res+sum(row))%MOD
print(res)

"""
print('------------')
cnt=0
for a in range(4):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                if (mp[a]+mp[b]+mp[c] in out) or (mp[b]+mp[c]+mp[d] in out): continue
                print(mp[a]+mp[b]+mp[c]+mp[d])
                cnt+=1
print(cnt)
"""

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

S = 'AGCT'  
num = [[[1]*4 for _ in range(4)] for _ in range(4)]

count = 0
if N == 3:
    print(61)
    exit()
for i in range(4, N+1):
    num_now = [[[0] * 4 for _ in range(4)] for _ in range(4)]
    for pre3 in range(4):
        for pre2 in range(4):
            for pre1 in range(4):
                for now in range(4):
                    now_S = S[pre2] + S[pre1] + S[now]
                    now_S2 = S[pre3] + S[pre2] + S[pre1]
                    if now_S2 != 'AGC' and now_S2 != 'GAC' and now_S2 != 'ACG' and now_S != 'AGC' and now_S != 'GAC' and now_S != 'ACG' and S[pre3] + S[pre1] + S[now] != 'AGC' and S[pre3] + S[pre2] + S[now] != 'AGC':
                        num_now[now][pre1][pre2] += num[pre1][pre2][pre3]
                        if i == N:
                            count += num[pre1][pre2][pre3]

    num = num_now.copy()


print(count%((10**9) + 7))

Solution (Python):
N=int(input())
INF=10**9+7
"""
lst=[[
]][i-2][i-1][i]0=A,1=G,2=C,3=T
"""
lst1=[]
lst2=[]
for i in range(4):
    lst2.append((i,0,1))
    lst2.append((i,1,0))
    lst1.append((i,0,2))
for i in range(1,4):
    lst2.append((0,i,1))
    lst2.append((0,1,i))
lst=[[[0 for i in range(4)] for j in range(4)]for k in range(4)]
lst[3][3][3]=1
def LST(lst):
    Lst=[[[0 for i in range(4)] for j in range(4)]for k in range(4)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in lst2:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
                    Lst[j][k][2]=0
                elif (i,j,k) in lst1:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
                    Lst[j][k][1]=0
                else:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
    return Lst
for n in range(N):
    lst=LST(lst)
sum=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            sum+=lst[i][j][k]
print(sum%INF)

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

dp = [[[[0 for i in range(4)] for i in range(4)] for i in range(4)] for i in range(n+1)]

for i in range(4):
  for j in range(4):
    for k in range(4):
      dp[0][i][j][k] = 1

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


for l in range(1, n+1):
  for m in range(4):
    for i in range(4):
      for j in range(4):
        for k in range(4):
          if i==2 and j==0 and m==1:
            dp[l][m][i][j] = 0
          elif i==0 and j==2 and m==1:
            dp[l][m][i][j] = 0
          elif i==1 and j==0 and m==2:
            dp[l][m][i][j] = 0
          elif i==2 and k==0 and m==1:
            dp[l][m][i][j] = 0
          elif j==2 and k==0 and m==1:
            dp[l][m][i][j] = 0
          else:
            dp[l][m][i][j] += dp[l-1][i][j][k]%mod

print(dp[n][3][3][3]%mod)

Solution (Python):
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

DIV = (10**9) +7

def make1d_arr(n,val=INF):
    return [val for i in xrange(n)]

def make2d_arr(w,h,val =INF):
    return [[val for i in xrange(w)]for i in xrange(h)]


N = int_raw()

dp = [0]*(N+1)
dp_a = [0]*(N+1)
dp_g = [0]*(N+1)

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



dp_a[1]=1
dp_a[2]=4
dp_a[3]=16

dp_g[1]=1
dp_g[2]=4
dp_g[3]=15






for i in xrange(4,N+1):
    dp_a[i] = dp[i-1] %DIV
    dp_g[i] = (dp[i-1] - dp[i-3] + dp_g[i-3]) %DIV
    dp [i] = (dp[i-1] + dp_a[i] + dp_g[i] + dp[i-1] - dp_a[i-3]*3 -dp_a[i-2]  - dp_g[i-2]  )%DIV

print dp[N]

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

DP = [[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] for i in range(101)]

DP[2] = [4,3,4,4,4,4,3,4,4,3,4,4,4,4,4,4]

for i in range(3,101):
    DP[i][0] = DP[i-1][0] + DP[i-1][4] + DP[i-1][8] + DP[i-1][12]
    DP[i][1] = DP[i-1][0] + DP[i-1][4] + DP[i-1][12]
    DP[i][2] = DP[i-1][0] + DP[i-1][4] + DP[i-1][8] + DP[i-1][12]
    DP[i][3] = DP[i-1][0] + DP[i-1][4] + DP[i-1][8] + DP[i-1][12]
    DP[i][4] = DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][5] = DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][6] = DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][7] = DP[i - 1][1] + DP[i - 1][5] + DP[i - 1][9] + DP[i - 1][13]
    DP[i][8] = DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]
    DP[i][9] = DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14] - DP[i - 2][3] - DP[i - 2][2]
    DP[i][10] = DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]
    DP[i][11] = DP[i - 1][2] + DP[i - 1][6] + DP[i - 1][10] + DP[i - 1][14]
    DP[i][12] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]
    DP[i][13] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15] - DP[i-2][2]
    DP[i][14] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]
    DP[i][15] = DP[i - 1][3] + DP[i - 1][7] + DP[i - 1][11] + DP[i - 1][15]

print(sum(DP[N-1]) % 1000000007)

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

dp_A = [1] + [0] * (N + 5)
dp_G = [1] + [0] * (N + 5)
dp_C = [1] + [0] * (N + 5)
dp_T = [1] + [0] * (N + 5)
dp_AG = [0] * (N + 5)
dp_AC = [0] * (N + 5)
dp_GA = [0] * (N + 5)
dp_AGA = [0] * (N + 5)
dp_AGG = [0] * (N + 5)
dp_AGT = [0] * (N + 5)
dp_AAG = [0] * (N + 5)
dp_AGG = [0] * (N + 5)
dp_ATG = [0] * (N + 5)
dp_ok = [4] + [0] * (N + 5)

for i in range(1, N):
    dp_A[i] = dp_ok[i - 1]
    dp_C[i] = dp_ok[i - 1] - dp_AG[i - 1] - dp_GA[i - 1] - dp_AGG[
        i - 1] - dp_AGT[i - 1] - dp_ATG[i - 1]
    dp_C[i] %= mod
    dp_G[i] = dp_ok[i - 1] - dp_AC[i - 1]
    dp_G[i] %= mod
    dp_T[i] = dp_ok[i - 1]
    dp_T[i] %= mod
    dp_AG[i] = dp_A[i - 1]
    dp_AG[i] %= mod
    dp_AC[i] = dp_A[i - 1] - dp_GA[i - 1]
    dp_AC[i] %= mod
    dp_GA[i] = dp_G[i - 1]
    dp_GA[i] %= mod
    dp_AGG[i] = dp_AG[i - 1]
    dp_AGG[i] %= mod
    dp_AGT[i] = dp_AG[i - 1]
    dp_AGT[i] %= mod
    dp_ATG[i] = dp_A[i - 2]
    dp_ATG[i] %= mod
    dp_ok[i] = dp_A[i] + dp_C[i] + dp_G[i] + dp_T[i]
    dp_ok[i] %= mod
print(dp_ok[N - 1])

Solution (Python):
N = int(input())
dp = [dict() for i in range(2)]

big = 10 ** 9 + 7

for a in ['A', 'C', 'G', 'T']:
    for b in ['A', 'C', 'G', 'T']:
        for c in ['A', 'C', 'G', 'T']:
            seq = a + b + c
            if seq != 'AGC' and seq != 'GAC' and seq != 'ACG':
                dp[0][seq] = 1
            else:
                dp[0][seq] = 0

def sum_of_dict(d):
    ans = 0
    for a in ['A', 'C', 'G', 'T']:
        for b in ['A', 'C', 'G', 'T']:
            for c in ['A', 'C', 'G', 'T']:
                seq = a+b+c
                ans += d[seq]
    return ans

def sum_of_dict_with(d, latter):
    ans = 0
    for a in ['A', 'C', 'G', 'T']:
        seq = a+latter
        ans += d[seq]
    return ans

for i in range(3, N):
    n = i % 2
    for a in ['A', 'C', 'G', 'T']:
        for b in ['A', 'C', 'G', 'T']:
            for c in ['A', 'C', 'G', 'T']:
                seq = a + b + c
                if seq == 'AGC' or seq == 'GAC' or seq == 'ACG':
                    dp[n][seq] = 0
                elif seq == 'TGC':
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1)%2], seq[:2]) - dp[(n-1)%2]['ATG']) % big
                elif seq == 'GGC':
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1)%2], seq[:2]) - dp[(n-1)%2]['AGG']) % big
                elif seq == 'GTC':
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1)%2], seq[:2]) - dp[(n-1)%2]['AGT']) % big
                else:
                    dp[n][seq] = (sum_of_dict_with(dp[(n-1) % 2], seq[:2])) % big

print(sum_of_dict(dp[(N-1)%2]) % big)

Solution (Python):
AAA = [1] * 101
AAC = [1] * 101
AAG = [1] * 101
AAT = [1] * 101
ACA = [1] * 101
ACC = [1] * 101
ACG = [0] * 101
ACT = [1] * 101
AGA = [1] * 101
AGC = [0] * 101
AGG = [1] * 101
AGT = [1] * 101
ATA = [1] * 101
ATC = [1] * 101
ATG = [1] * 101
ATT = [1] * 101
CAA = [1] * 101
CAC = [1] * 101
CAG = [1] * 101
CAT = [1] * 101
CCA = [1] * 101
CCC = [1] * 101
CCG = [1] * 101
CCT = [1] * 101
CGA = [1] * 101
CGC = [1] * 101
CGG = [1] * 101
CGT = [1] * 101
CTA = [1] * 101
CTC = [1] * 101
CTG = [1] * 101
CTT = [1] * 101
GAA = [1] * 101
GAC = [0] * 101
GAG = [1] * 101
GAT = [1] * 101
GCA = [1] * 101
GCC = [1] * 101
GCG = [1] * 101
GCT = [1] * 101
GGA = [1] * 101
GGC = [1] * 101
GGG = [1] * 101
GGT = [1] * 101
GTA = [1] * 101
GTC = [1] * 101
GTG = [1] * 101
GTT = [1] * 101
TAA = [1] * 101
TAC = [1] * 101
TAG = [1] * 101
TAT = [1] * 101
TCA = [1] * 101
TCC = [1] * 101
TCG = [1] * 101
TCT = [1] * 101
TGA = [1] * 101
TGC = [1] * 101
TGG = [1] * 101
TGT = [1] * 101
TTA = [1] * 101
TTC = [1] * 101
TTG = [1] * 101
TTT = [1] * 101



for i in range(4, 101):

	AAA[i] = AAA[i-1] + CAA[i-1] + GAA[i-1] + TAA[i-1]
	AAC[i] = AAA[i]
	AAG[i] = AAA[i]
	AAT[i] = AAA[i]
	ACA[i] = AAC[i-1] + CAC[i-1]  + TAC[i-1]
	ACC[i] = ACA[i]
	ACG[i] = 0
	ACT[i] = ACA[i]
	AGA[i] = AAG[i-1] + CAG[i-1] + GAG[i-1] + TAG[i-1]
	AGC[i] = 0
	AGG[i] = AGA[i]
	AGT[i] = AGA[i]
	ATA[i] = AAT[i-1] + CAT[i-1] + GAT[i-1] + TAT[i-1]
	ATC[i] = ATA[i]
	ATG[i] = ATA[i]
	ATT[i] = ATA[i]

	CAA[i] = ACA[i-1] + CCA[i-1] + GCA[i-1] + TCA[i-1]
	CAC[i] = CAA[i]
	CAG[i] = CAA[i]
	CAT[i] = CAA[i]
	CCA[i] = ACC[i-1] + CCC[i-1] + GCC[i-1] + TCC[i-1]
	CCC[i] = CCA[i]
	CCG[i] = CCA[i]
	CCT[i] = CCA[i]
	CGA[i] = 0 + CCG[i-1] + GCG[i-1] + TCG[i-1]
	CGC[i] = CGA[i]
	CGG[i] = CGA[i]
	CGT[i] = CGA[i]
	CTA[i] = ACT[i-1] + CCT[i-1] + GCT[i-1] + TCT[i-1]
	CTC[i] = CTA[i]
	CTG[i] = CTA[i]
	CTT[i] = CTA[i]

	GAA[i] = AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GAC[i] = 0 
	GAG[i] = AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GAT[i] = AGA[i-1] + CGA[i-1] + GGA[i-1] + TGA[i-1]
	GCA[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GCC[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GCG[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GCT[i] = 0        + CGC[i-1] + GGC[i-1] + TGC[i-1]
	GGA[i] = AGG[i-1] + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GGC[i] = 0        + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GGG[i] = AGG[i-1] + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GGT[i] = AGG[i-1] + CGG[i-1] + GGG[i-1] + TGG[i-1]
	GTA[i] = AGT[i-1] + CGT[i-1] + GGT[i-1] + TGT[i-1]
	GTC[i] = 0        + CGT[i-1] + GGT[i-1] + TGT[i-1]
	GTG[i] = AGT[i-1] + CGT[i-1] + GGT[i-1] + TGT[i-1]
	GTT[i] = AGT[i-1] + CGT[i-1] + GGT[i-1] + TGT[i-1]

	TAA[i] = ATA[i-1] + CTA[i-1] + GTA[i-1] + TTA[i-1]
	TAC[i] = TAA[i]
	TAG[i] = TAA[i]
	TAT[i] = TAA[i]
	TCA[i] = ATC[i-1] + CTC[i-1] + GTC[i-1] +  TTC[i-1]
	TCC[i] = TCA[i]
	TCG[i] = TCA[i]
	TCT[i] = TCA[i]
	TGA[i] = ATG[i-1] + CTG[i-1] + GTG[i-1] + TTG[i-1]
	TGC[i] = 0        + CTG[i-1] + GTG[i-1] + TTG[i-1]
	TGG[i] = TGA[i]
	TGT[i] = TGA[i]
	TTA[i] = ATT[i-1] + CTT[i-1] + GTT[i-1] + TTT[i-1]
	TTC[i] = TTA[i]
	TTG[i] = TTA[i]
	TTT[i] = TTA[i]


n = int(input())
temp = 0 \
 + AAA[n] \
 + AAC[n] \
 + AAG[n] \
 + AAT[n] \
 + ACA[n] \
 + ACC[n] \
 + ACG[n] \
 + ACT[n] \
 + AGA[n] \
 + AGC[n] \
 + AGG[n] \
 + AGT[n] \
 + ATA[n] \
 + ATC[n] \
 + ATG[n] \
 + ATT[n] \
 + CAA[n] \
 + CAC[n] \
 + CAG[n] \
 + CAT[n] \
 + CCA[n] \
 + CCC[n] \
 + CCG[n] \
 + CCT[n] \
 + CGA[n] \
 + CGC[n] \
 + CGG[n] \
 + CGT[n] \
 + CTA[n] \
 + CTC[n] \
 + CTG[n] \
 + CTT[n] \
 + GAA[n] \
 + GAC[n] \
 + GAG[n] \
 + GAT[n] \
 + GCA[n] \
 + GCC[n] \
 + GCG[n] \
 + GCT[n] \
 + GGA[n] \
 + GGC[n] \
 + GGG[n] \
 + GGT[n] \
 + GTA[n] \
 + GTC[n] \
 + GTG[n] \
 + GTT[n] \
 + TAA[n] \
 + TAC[n] \
 + TAG[n] \
 + TAT[n] \
 + TCA[n] \
 + TCC[n] \
 + TCG[n] \
 + TCT[n] \
 + TGA[n] \
 + TGC[n] \
 + TGG[n] \
 + TGT[n] \
 + TTA[n] \
 + TTC[n] \
 + TTG[n] \
 + TTT[n]

print(temp % (1000000007))

Solution (Python):
n = int(input())
mod = 10**9 + 7
d = {}
cnt = 0
for i in 'ATGC':
  for j in 'ATGC':
    for k in 'ATGC':
      s = i+j+k
      d[s] = cnt
      cnt += 1
dp = [[0 for j in range(n-2)] for i in range(64)]
for i in 'ATGC':
  for j in 'ATGC':
    for k in 'ATGC':
      s = i+j+k
      if s!='AGC' and s!='ACG' and s!='GAC':
        dp[d[s]][0] = 1
for i in range(n-3):
  for x in 'ATGC':
    for y in 'ATGC':
      for z in 'ATGC':
        for w in 'ATGC':
          s = y+z+w
          if s!='AGC' and s!='ACG' and s!='GAC' and x+s!='AGAC' and x+s!='AGTC' and x+s!='AGGC' and x+s!='ATGC':
            dp[d[y+z+w]][i+1] += dp[d[x+y+z]][i]
            dp[d[y+z+w]][i+1] %= mod
ans = 0
for i in range(64):
  ans += dp[i][n-3]
  ans %= mod
print(ans)