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):
n = int(input())
MOD = 10**9+7


dp = [[0]*4 for i in range(100)]


for i in range(n):
    if i == 0:
        for j in range(4):
            dp[i][j] = 1
    elif i == 1:
        for j in range(4):
            dp[i][j] = sum(dp[i-1])
    elif i == 2:
        for j in range(4):
            if j == 0 or j == 3:
                dp[i][j] = sum(dp[i-1])
            if j == 1:
                dp[i][j] = sum(dp[i-1]) - 2
            if j == 2:
                dp[i][j] = sum(dp[i-1]) - 1
    else:
        for j in range(4):
            if j == 0 or j == 3:
                dp[i][j] = sum(dp[i-1])
            if j == 1:
                dp[i][j] = sum(dp[i-1]) - dp[i-2][0] - dp[i-2][2]-dp[i-3][0]*3
            if j == 2:
                dp[i][j] = sum(dp[i-1]) - (sum(dp[i-3]) - dp[i-3][2])        
print(sum(dp[n-1])%MOD)

Solution (Python):
n = int(input())
MOD = 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):
    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):
mod = 10 ** 9 + 7


def is_ok(last4):
    for i in range(4):
        t = list(last4)
        if i != 3:
            t[i], t[i + 1] = t[i + 1], t[i]
            
            
        if 'AGC' in ''.join(t):
            return False
    return True


def dfs(length, last3):
    
    if last3 in m[length]:
        return m[length][last3]

    if length == n:
        return 1

    res = 0
    for c in 'ACGT':
        
        if is_ok(last3 + c):
            res += dfs(length + 1, last3[1:] + c)
            res %= mod

    m[length][last3] = res
    return res


n = int(input())
m = [{} for _ in range(n + 1)]
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):
A = [0, 1, 4]
G = [0, 1, 4]
C = [0, 1, 4]
T = [0, 1, 4]
AG = [0, 0, 1]
GA = [0, 0, 1]
AC = [0, 0, 1]
AT = [0, 0, 1]
AGG = [0, 0, 0]
ATG = [0, 0, 0]
AGT = [0, 0, 0]
for i in range(2, 100):
	A.append(A[i]+G[i]+C[i]+T[i])
	G.append(A[i]+G[i]+C[i]+T[i]-AC[i])
	C.append(A[i]+G[i]+C[i]+T[i]-AG[i]-GA[i]-AGG[i]-ATG[i]-AGT[i])
	T.append(A[i]+G[i]+C[i]+T[i])
	AG.append(A[i])
	GA.append(G[i])
	AC.append(A[i]-GA[i])
	AT.append(A[i])
	AGG.append(AG[i])
	ATG.append(AT[i])
	AGT.append(AG[i])
N = int(input())
print((A[N]+G[N]+C[N]+T[N])%(10**9+7))

Solution (Python):
N=int(input())
d={}
mod=10**9+7
from itertools import product
import re
for t in product('ATGC',repeat=3):
    s=''.join(t)
    d[s]=[0]*(N-2)
    d[s][0]=0 if s in ['AGC','ACG','GAC'] else 1
p=re.compile('.AGC|.ACG|.GAC|A.GC|AG.C')
for i in range(N-3):
    for t in product('ATGC',repeat=3):
        for c in 'ATGC':
            s=''.join(t)+c
            if p.search(s)==None:
                d[s[1:]][i+1]=(d[s[1:]][i+1]+d[s[:-1]][i])%mod
print(sum([i[-1] for i in d.values()])%mod)

Solution (Python):



def main():
    n = int(input())
    MOD = 10 ** 9 + 7

    dpa = [0, 0, 1]
    dpc = [0, 0, 1]
    dpg = [0, 0, 1]
    dpt = [0, 0, 1]
    for i in range(2, n + 2):
        total = dpa[i] + dpc[i] + dpg[i] + dpt[i]
        if i == n + 1:
            break
        dpa.append(total)
        dpc.append(total - dpa[i-1] - dpg[i-1] - 3 * dpa[i-2])
        dpg.append(total - dpa[i-1] + dpg[i-2])
        dpt.append(total)
    print(total % MOD)


main()

Solution (Python):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

def ok(S):
    for ng in ['AGC', 'GAC', 'ACG']:
        if S[1:] == ng or S[:3] == ng:
            return False
    if S[0] == 'A' and S[2:] == 'GC':
        return False
    if S[:2] == 'AG' and S[3] == 'C':
        return False
    return True


memo = {}
def find(i, prev):
    if (i, prev) in memo:
        return memo[(i, prev)]

    if i == N:
        return 1

    res = 0
    for c in 'ACGT':
        if ok(prev + c):
           res += find(i+1, prev[1:] + c)

    res %= 1000000007
    memo[(i, prev)] = res
    return res

print(find(0, 'TTT'))

Solution (Python):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

def ok(S):
    for ng in ['AGC', 'GAC', 'ACG']:
        if S[1:] == ng or S[:3] == ng:
            return False
    if S[0] == 'A' and S[2:] == 'GC':
        return False
    if S[:2] == 'AG' and S[3] == 'C':
        return False
    return True


memo = {}
def find(i, prev):
    if (i, prev) in memo:
        return memo[(i, prev)]

    if i == N:
        return 1

    res = 0
    for c in 'ACGT':
        if ok(prev + c):
           res += find(i+1, prev[1:] + c)

    res %= 1000000007
    memo[(i, prev)] = res
    return res

print(find(0, 'TTT'))

Solution (Python):
def main():
    n = int(input())
    MOD = 10 ** 9 + 7
    note = [{} 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):
        if last3 in note[cur]:
            return note[cur][last3]
        if cur == n:
            return 1
        ret = 0
        for c in 'ACGT':
            if ok(last3 + c):
                ret += dfs(cur + 1, last3[1:] + c)
                ret %= MOD
        note[cur][last3] = ret
        return ret

    print(dfs(0, 'TTT'))


main()

Solution (Python):
import re
import functools

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


@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C', last3 + c):
            ret += dfs(cur + 1, last3[1:] + c)
    return ret % MOD


print(dfs(0, 'TTT'))

Solution (Python):
def main():

    """ convenient functions
    
    
    
    
    
    """

    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter
    
    
    from functools import reduce
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    """ initialize variables and set inputs
    
        
        
    
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    if __name__ != '__main__':
        
        sys.stdin = open('sample.txt')

    
    

    N = int(r())
    
    
    
    
    dp = [[0]*100 for _ in range(16)]
    anslist = [0] * N
    anslist[0] = 4
    anslist[1] = 16
    for i in range(16):
        dp[i][1] = 1
        dp[i][2] = 4
    dp[1][2] = 3
    dp[6][2] = 3
    dp[9][2] = 3
    for j in range(3, 100):
        for i in range(16):
            for k in range(4):
                dp[i][j] += dp[i//4+4*k][j-1] % MOD
            if i == 1:
                dp[i][j] -= dp[8][j-1] % MOD
            elif i == 6:
                dp[i][j] -= dp[1][j-1] % MOD
            elif i == 9:
                dp[i][j] -= dp[2][j-1] % MOD
            
            if i == 9:
                dp[i][j] -= (dp[2][j-2]+dp[3][j-2])
            
            if i == 13:
                dp[i][j] -= dp[2][j-2]
        
    if N == 1:
        print(4)
    elif N == 2:
        print(16)
    else:
        ans = 0
        for i in range(16):
            ans += dp[i][N-1]
        print(ans%MOD)
    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """

if __name__ == '__main__':
    main()

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

MOD = 10**9 + 7

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

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

def search(currentIndex, prevText) :
    if currentIndex >= N :
        return 1
    if prevText in memo[currentIndex] :
        return memo[currentIndex][prevText]
    ret = 0

    for addText in 'ACGT' :
        if isValid(prevText + addText) :
            ret = (ret + search(currentIndex + 1,prevText[1:] + addText)) % MOD  

    memo[currentIndex][prevText] = ret
    return ret

print(search(0,'ZZZ'))

Solution (Python):
n = int(input())
memo = [dict() for _ in range(n+1)]

memo[0][""] = 1

def ok(last4):
  for ng in ["AGC","ACG","GAC"]:
    if last4.find(ng)>=0:
      return False
  if len(last4) < 4:
    return True
  if last4[0] =="A" and last4[2:]=="GC":
    return False
  if last4[:2]=="AG" and last4[3]== "C":
    return False
  return True

for i in range(1,n+1):
  for last3, v in memo[i-1].items():
    for c in "ATGC":
      if ok(last3+c):
        try:
          memo[i][last3[-2:]+c] += v
        except KeyError:
          memo[i][last3[-2:]+c] = v

MOD = int(10**9+7)
ans = 0
for v in memo[n].values():
  ans += v

print(ans%MOD)

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

mod = 10**9+7

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 len in range(N):
    
    for c1 in range(4):
        
        for c2 in range(4):
            
            for c3 in range(4):
                if dp[len][c1][c2][c3] == 0:
                    continue
                for c0 in range(4):
                    if c0 ==2 and c1 == 1 and c2 == 0:
                        continue
                    if c0 ==1 and c1 == 2 and c2 == 0:
                        continue
                    if c0 ==2 and c1 == 0 and c2 == 1:
                        continue
                    if c0 ==2 and c1 == 1 and c3 == 0:
                        continue
                    if c0 ==2 and c2 == 1 and c3 == 0:
                        continue
                    dp[len+1][c0][c1][c2] += dp[len][c1][c2][c3]
                    dp[len+1][c0][c1][c2] %= mod


ans = 0

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

Solution (Python):
n=int(input())
m=10**9+7
dp=[{} for _ in range(n+1)]

def ok(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")>=1:
            return False
    return True

def dfs(cur, last3):
    if last3 in dp[cur]:
        return dp[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)
            ret%=m
        dp[cur][last3]=ret
    return ret

print(dfs(0, "___"))

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

MOD = 10**9 + 7

dp =  [ [ [ [ 0 for i in range(5) ] for j in range(5)] for p in range(5)] for q 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 p in range(5):
                for q in range(1,5):
                    if i == 1 and j == 2 and q == 3:
                        continue
                    if j == 1 and p == 3 and q == 2:
                        continue
                    if j == 2 and p == 1 and q == 3:
                        continue
                    if j == 1 and p == 2 and q == 3:
                        continue
                    if i == 1 and p == 2 and q == 3:
                        continue

                    dp[n+1][j][p][q] =(dp[n+1][j][p][q] + dp[n][i][j][p]) % MOD

ans = 0
for i in range(1,5):
    for j in range(1,5):
        for p in range(1,5):
            ans = (ans + dp[N][i][j][p]) % MOD
print(ans%MOD)

Solution (Python):
mod=10**9+7
n=int(input())
DP=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      DP[3][i][j][k]=1
DP[3][0][1][2]=0
DP[3][0][2][1]=0  
DP[3][2][0][1]=0  
for i in range(3,n):
  DP[i+1][0][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][0][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][0][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][0][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][0][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][0][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][0][1][2]=0
  DP[i+1][0][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][0][2][0]=DP[i][2][0][0]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][0][2][1]=0
  DP[i+1][0][2][2]=DP[i][2][2][0]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][0][2][3]=DP[i][2][3][0]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][0][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][0][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][0][3][2]=DP[i][3][2][0]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][0][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][1][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][1][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][1][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][1][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][1][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][1][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][1][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][1][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][1][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][1][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][1][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][1][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][1][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][1][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][1][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][1][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][2][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][2][0][1]=0
  DP[i+1][2][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][2][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][2][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][2][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][2][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][2][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][2][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][2][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][2][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][2][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][2][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][2][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][2][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][2][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][3][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][3][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][3][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][3][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][3][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][3][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][3][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][3][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][3][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][3][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][3][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][3][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][3][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][3][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][3][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][3][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=DP[n][i][j][k]%mod
print(ans%mod)

Solution (Python):
mod=10**9+7
n=int(input())
DP=[[[[0]*4 for i in range(4)] for j in range(4)] for k in range(n+1)]
for i in range(4):
  for j in range(4):
    for k in range(4):
      DP[3][i][j][k]=1
DP[3][0][1][2]=0
DP[3][0][2][1]=0  
DP[3][2][0][1]=0  
for i in range(3,n):
  DP[i+1][0][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][0][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][0][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][0][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][0][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][0][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][0][1][2]=0
  DP[i+1][0][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][0][2][0]=DP[i][2][0][0]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][0][2][1]=0
  DP[i+1][0][2][2]=DP[i][2][2][0]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][0][2][3]=DP[i][2][3][0]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][0][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][0][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][0][3][2]=DP[i][3][2][0]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][0][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][1][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][1][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][1][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][1][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][1][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][1][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][1][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][1][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][1][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][1][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][1][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][1][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][1][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][1][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][1][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][1][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][2][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][2][0][1]=0
  DP[i+1][2][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][2][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][2][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][2][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][2][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][2][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][2][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][2][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][2][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][2][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][2][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][2][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][2][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][2][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]

  DP[i+1][3][0][0]=DP[i][0][0][0]+DP[i][0][0][1]+DP[i][0][0][2]+DP[i][0][0][3]
  DP[i+1][3][0][1]=DP[i][0][1][0]+DP[i][0][1][1]+DP[i][0][1][2]+DP[i][0][1][3]
  DP[i+1][3][0][2]=DP[i][0][2][0]+DP[i][0][2][1]+DP[i][0][2][2]+DP[i][0][2][3]
  DP[i+1][3][0][3]=DP[i][0][3][0]+DP[i][0][3][1]+DP[i][0][3][2]+DP[i][0][3][3]
  DP[i+1][3][1][0]=DP[i][1][0][0]+DP[i][1][0][1]+DP[i][1][0][2]+DP[i][1][0][3]
  DP[i+1][3][1][1]=DP[i][1][1][0]+DP[i][1][1][1]+DP[i][1][1][2]+DP[i][1][1][3]
  DP[i+1][3][1][2]=DP[i][1][2][0]+DP[i][1][2][1]+DP[i][1][2][2]+DP[i][1][2][3]
  DP[i+1][3][1][3]=DP[i][1][3][0]+DP[i][1][3][1]+DP[i][1][3][2]+DP[i][1][3][3]
  DP[i+1][3][2][0]=DP[i][2][0][0]+DP[i][2][0][1]+DP[i][2][0][2]+DP[i][2][0][3]
  DP[i+1][3][2][1]=DP[i][2][1][0]+DP[i][2][1][1]+DP[i][2][1][2]+DP[i][2][1][3]
  DP[i+1][3][2][2]=DP[i][2][2][0]+DP[i][2][2][1]+DP[i][2][2][2]+DP[i][2][2][3]
  DP[i+1][3][2][3]=DP[i][2][3][0]+DP[i][2][3][1]+DP[i][2][3][2]+DP[i][2][3][3]
  DP[i+1][3][3][0]=DP[i][3][0][0]+DP[i][3][0][1]+DP[i][3][0][2]+DP[i][3][0][3]
  DP[i+1][3][3][1]=DP[i][3][1][0]+DP[i][3][1][1]+DP[i][3][1][2]+DP[i][3][1][3]
  DP[i+1][3][3][2]=DP[i][3][2][0]+DP[i][3][2][1]+DP[i][3][2][2]+DP[i][3][2][3]
  DP[i+1][3][3][3]=DP[i][3][3][0]+DP[i][3][3][1]+DP[i][3][3][2]+DP[i][3][3][3]
ans=0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans+=DP[n][i][j][k]%mod
print(ans%mod)

Solution (Python):
def elongation(n):
    NG=["AAGC","GAGC","TAGC","CAGC","AGAC","GGAC","CGAC","TGAC","AACG","GACG","CACG","TACG","AGGC","ATGC","AGTC"]
    trinucleotide={"TTT":1}
    new_trinucleotide={}
    MOD=10**9+7
    for k in range(n):
        for i in trinucleotide:
            for j in "AGCT":
                new=i+j
                if new in NG:
                    pass
                else:
                    if new[1:] in new_trinucleotide:
                         new_trinucleotide[new[1:]]=(new_trinucleotide[new[1:]]+trinucleotide[i])
                    else:
                         new_trinucleotide[new[1:]]=trinucleotide[i]
        trinucleotide=new_trinucleotide
        new_trinucleotide={}
    return(sum(trinucleotide.values())%MOD)

print(elongation(int(input())))

Solution (Python):
N = int(input())
c = 'AGC'
p = ['A', 'C', 'G', 'T']
s = 'XXX'
memo = [{} for _ in range(N)]
MOD = 10 ** 9 + 7


def agc_check(t):
    t1 = t[1] + t[0] + t[2] + t[3]
    t2 = t[0] + t[2] + t[1] + t[3]
    t3 = t[0] + t[1] + t[3] + t[2]
    if (c in t) or (c in t1) or (c in t2) or (c in t3):
        return 0
    else:
        return 1


def agc_plus(t, cur):
    if cur == N:
        return 1
    if t in memo[cur]:
        return memo[cur][t]
    r = 0
    for tt in p:
        if agc_check(t + tt):
            r += agc_plus(t[1:] + tt, cur + 1)
    memo[cur][t] = r % MOD
    return memo[cur][t]


ans = agc_plus(s, 0)
print(ans)

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

def d(s):
    if "AGC" in s:
        return False
    for i in range(3):
        l=list(s)
        l[i],l[i+1]=l[i+1],l[i]
        if "AGC" in "".join(l):
            return False
    return True

m=[{} for i in range(n+1)]
def f(num,s):
    if s in m[num]:
        return m[num][s]
    if num==n:
        return 1
    ans=0
    for c in "ACGT":
        if d(s+c):
            ans=(ans+f(num+1,s[1:3]+c))%mod
    m[num][s]=ans
    return ans

print(f(0,"PPP"))