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

Solution (Python):



mod = 1000000007
N = int(input())

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


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


for n in range(N):
  
  for c1 in range(4):
    
    for c2 in range(4):
      
      for c3 in range(4):
        
        if dp[n][c1][c2][c3] == 0: continue

        
        for a in range(4):
          
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

          dp[n+1][a][c1][c2] += dp[n][c1][c2][c3]

ans = 0

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

print(ans % mod)

Solution (Python):

mod = 1000000007
N = int(input())

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


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


for n in range(N):
  
  for c1 in range(4):
    
    for c2 in range(4):
      
      for c3 in range(4):
        
        if dp[n][c1][c2][c3] == 0: continue

        
        for a in range(4):
          
          if(c2 == 0 and c1 == 1 and a == 2): continue
          if(c2 == 0 and c1 == 2 and a == 1): continue
          if(c2 == 1 and c1 == 0 and a == 2): continue
          if(c3 == 0 and c1 == 1 and a == 2): continue
          if(c3 == 0 and c2 == 1 and a == 2): continue

          dp[n+1][a][c1][c2] += dp[n][c1][c2][c3]
          dp[n+1][a][c1][c2] %= mod

ans = 0

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

print(ans)

Solution (Python):
n=int(input())
m=[{}for i in range(n+1)]
w=10**9+7
def f(s):
    for i in range(4):
        t=list(s)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>0:
            return False
    return True
def a(p,q):
    if q in m[p]:
        return m[p][q]
    if p==n:
        return 1
    r=0
    for i in "AGCT":
        if f(q+i):
            r=(r+a(p+1,q[1:]+i))%w
    m[p][q]=r
    return r
print(a(0,"WHY"))

Solution (Python):
def main():
    '''
    A => 0
    C => 1
    G => 2
    T => 3
    '''
    N = int(input())
    MOD = 10 ** 9 + 7
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(105)]
    
    dp[0][3][3][3] = 1

    for n in range(N):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for new in range(4):
                        if j == 0 and k == 2 and new == 1:
                            continue
                        if j == 2 and k == 0 and new == 1:
                            continue
                        if j == 0 and k == 1 and new == 2:
                            continue
                        if i == 0 and k == 2 and new == 1:
                            continue
                        if i == 0 and j == 2 and new == 1:
                            continue

                        dp[n+1][j][k][new] += dp[n][i][j][k]
                        dp[n+1][j][k][new] %= 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 %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
dp = [[0 for _ in range(4**4)] for _ in range(N-3)]
cau = [6, 9, 24, 25, 26, 27, 33, 36, 37, 38, 39, 41, 45, 57, 70, 73, 97, 132, 133, 134, 135, 137, 161, 198, 201, 225]
if N==3:
    print(61)
    exit()

for i in range(4**4):
    dp[0][i] = 1 - cau.count(i)
for i in range(N-4):
    for j in range(4**4):
        if j in cau:
            dp[i+1][j] = 0
            continue
        tgt = 4*(j%(4**3))
        tgt_list = [tgt+i for i in range(4) if tgt+i not in cau]
        for elem in tgt_list:
            dp[i+1][j] += dp[i][elem]
        dp[i+1][j] = dp[i+1][j]%(10**9+7)
print(sum(dp[N-4])%(10**9+7))
"""

res = [[] for _ in range(8)]
for j in range(4**4):
    j1 = j//(4**3)
    j2 = j%(4**3)//(4**2)
    j3 = j%(4**2)//4
    j4 = j%4
    
    if j2==0 and j3==2 and j4==1:
        res[0].append(j)
    if j1==0 and j3==2 and j4==1:
        res[1].append(j)
    if j1==0 and j2==2 and j4==1:
        res[2].append(j)
    if j2==2 and j3==0 and j4==1:
        res[3].append(j)
    if j2==0 and j3==1 and j4==2:
        res[4].append(j)
    if j1==0 and j2==2 and j3==1:
        res[5].append(j)
    if j1==2 and j2==0 and j3==1:
        res[6].append(j)
    if j1==0 and j2==1 and j3==2:
        res[7].append(j)
print(res)
"""

Solution (Python):
import numpy as np

MOD = 10**9+7

N = int(input())
DP = [{} for i in range(N+1)]

out = []
AGCT = []
for i in "AGCT":
    for j in "AGCT":
        for k in "AGCT":
            for l in "AGCT":
                str = [i,j,k,l]
                AGCT.append(''.join(str))
                if ''.join(str).count("AGC") >= 1:
                    out.append(''.join(str))
                    continue
                for x  in range(3):
                    hoge = str.copy()
                    hoge[x], hoge[x+1] = hoge[x+1], hoge[x]
                    if ''.join(hoge).count("AGC") >= 1:
                        out.append(''.join(str))
                        break
DP[0]["TTTT"] = 1
for i in range(N):
    for key in AGCT:
        DP[i+1][key] = 0
    for key in DP[i]:
        for c in "AGCT":
            DP[i+1][(key+c)[-4:]] += DP[i][key]
            DP[i+1][(key+c)[-4:]] %= MOD
    for key in out:
        DP[i+1][key] = 0
ans = 0
for i in DP[-1]:
    ans += DP[-1][i]
    ans %= MOD
print(ans)

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):
N = int(input())
dp = [[[[0 for a in range(4)] for b in range(4)] for c in range(4)] for i in range(100+1)]


mod = 10**9 + 7

for a in range(4):
  for b in range(4):
    for c in range(4):
      dp[3][a][b][c] = 1
dp[3][0][1][2] = 0
dp[3][0][2][1] = 0
dp[3][1][0][2] = 0


for i in range(4,100+1):
  for a in range(4):
    for b in range(4):
      for c in range(4):
        for j in range(4):
          dp[i][a][b][c] += dp[i-1][j][a][b]
          if b == 1 and c == 2 and j == 0:
            dp[i][a][b][c] -= dp[i-1][j][a][b]
          if a == 1 and c == 2 and j == 0:
            dp[i][a][b][c] -= dp[i-1][j][a][b]
          if a == 1 and b == 1 and c == 2 and j == 0:
            dp[i][a][b][c] += dp[i-1][j][a][b]
          dp[i][a][b][c] %= mod
  dp[i][0][1][2] = 0
  dp[i][1][0][2] = 0
  dp[i][0][2][1] = 0

answer = 0
for a in range(4):
  for b in range(4):
    for c in range(4):
      answer += dp[N][a][b][c]
answer %= mod
print(answer)

Solution (Python):
n = int(input())
mask = 0b111111
mod = 10**9+7
dp = [[0]*4**3 for _ in range(n+1)]
dp[0][63] = 1
for i in range(n):
  for bit in range(4**3):
    for x in range(4):
      nb = bit<<2&63|x
      f = nb == 6 or nb == 9 or nb == 33
      f |= bit&51 == 2 and x == 1
      f |= bit&60 == 8 and x == 1
      if f:
        continue
      dp[i+1][nb] += dp[i][bit]
      dp[i+1][nb] %= mod
print(sum(dp[-1])%mod)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()


dp = list4d(N+1, 5, 5, 5, 0)
dp[0][0][0][0] = 1


for i in range(N):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                
                for m in range(1, 5):
                    
                    if k == 1 and l == 3 and m == 2:
                        continue
                    
                    elif k == 1 and l == 2 and m == 3:
                        continue
                    
                    elif k == 3 and l == 1 and m == 2:
                        continue
                    
                    elif j == 1 and l == 3 and m == 2:
                        continue
                    
                    elif j == 1 and k == 3 and m == 2:
                        continue
                    dp[i+1][k][l][m] += dp[i][j][k][l]
                    dp[i+1][k][l][m] %= MOD
ans = 0
for j in range(5):
    for k in range(5):
        for l in range(5):
            ans += dp[N][j][k][l]
            ans %= MOD
print(ans)

Solution (Python):






N = int(input())






MOD = 10 ** 9 + 7





char = ['A', 'C', 'G', 'T']
S = [c1 + c2 + c3 for c1 in char for c2 in char for c3 in char]
S





ng3 = ['AGC', 'GAC', 'ACG']
ng4 = [c + ng for c in char for ng in ng3] + [ng + c for c in char for ng in ng3] + ['A' + c + 'GC' for c in char] + ['AG' + c + 'C' for c in char]
ng4 = set(ng4)
ng4





dict1 = {s: 1 if s not in ng3 else 0 for s in S}





for _ in range(N - 3):
    dict2 = {}

    for s in S:
        val = 0
        for c in char:
            if c + s not in ng4:
                val = (val + dict1[c + s[:2]]) % MOD
        dict2[s] = val
    dict1 = dict2





ans = 0
for s in dict1.keys():
    ans = (ans + dict1[s]) % MOD
print(ans)

Solution (Python):
def p_d():
    n = int(input())
    mod = 10 ** 9 + 7
    
    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if j == 1 and k == 2 and l == 3:
                    continue
                if j == 2 and k == 1 and l == 3:
                    continue
                if j == 1 and k == 3 and l == 2:
                    continue
                dp[3][j][k][l] = 1
    for i in range(4, n + 1):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    for m in range(4):
                        if j == 1 and k == 2 and l == 3:
                            continue
                        if j == 2 and k == 1 and l == 3:
                            continue
                        if j == 1 and k == 3 and l == 2:
                            continue
                        if m == 1 and k == 2 and l == 3:
                            continue
                        if m == 1 and j == 2 and l == 3:
                            continue
                        dp[i][j][k][l] += dp[i - 1][m][j][k]
                        dp[i][j][k][l] %= mod

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


if __name__ == '__main__':
    p_d()

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

for s_len in range(N+1):
    for c1 in range(4):
        dp[s_len].append([])
        for c2 in range(4):
            dp[s_len][c1].append([0,0,0,0])
dp[0][3][3][3] = 1            

for s_len in range(N):
    for c4 in range(4):
        for c3 in range(4):
            for c2 in range(4):
                if dp[s_len][c2][c3][c4] == 0:
                    continue
                for c1 in range(4):
                    if c3 == 0 and c2 == 1 and c1 == 2:
                        continue
                    if c3 == 1 and c2 == 0 and c1 == 2:
                        continue
                    if c3 == 0 and c2 == 2 and c1 == 1:
                        continue
                    if c4 == 0 and c2 == 1 and c1 == 2:
                        continue
                    if c4 == 0 and c3 == 1 and c1 == 2:
                        continue
                    dp[s_len+1][c1][c2][c3] += dp[s_len][c2][c3][c4]
                    current_num = dp[s_len][c2][c3][c4]
                    dp[s_len+1][c1][c2][c3] = dp[s_len+1][c1][c2][c3]%mod

ans = 0

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

Solution (Python):
def solve():
    from functools import lru_cache

    mod = 10 ** 9 + 7

    def is_ok(last4: str) -> bool:
        if 'AGC' in last4:
            return False
        for j in range(3):
            t = list(last4)
            t[j], t[j + 1] = t[j + 1], t[j]
            if 'AGC' in ''.join(t):
                return False
        return True

    @lru_cache(maxsize=None)
    def dfs(curr: int = 0, last3: str = 'XXX'):
        ret = 0
        if curr == n:
            return 1
        for c in 'ACGT':
            last4 = last3 + c
            if is_ok(last4):
                ret += dfs(curr + 1, last4[1:])
        return ret % mod

    n = int(input())
    print(dfs())


solve()

Solution (Python):
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





def chk(s):

  if   s[0] == 3 and s[1] == 2 and s[3] == 1: return False
  elif s[0] == 3 and s[2] == 2 and s[3] == 1: return False
  elif s[1] == 3 and s[2] == 1 and s[3] == 2: return False
  elif s[1] == 2 and s[2] == 3 and s[3] == 1: return False
  elif s[1] == 3 and s[2] == 2 and s[3] == 1: return False
  else: return True

def dfs(c, j, k, l):
  for m in range(4):
    if chk([j, k, l, m]):
      dp[c][k][l][m] += dp[c-1][j][k][l]

for i in range(1, n+1):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        dfs(i, j, k, l)

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

Solution (Python):

n = int(input())
mod = 10 ** 9 + 7
now = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
now[3][3][3] = 1

boo = [[0,0,1,2],[1,0,1,2],[2,0,1,2],[3,0,1,2],
       [0,0,1,2],[0,1,1,2],[0,2,1,2],[0,3,1,2],
       [0,1,0,2],[0,1,1,2],[0,1,2,2],[0,1,3,2],
       [0,1,0,2],[1,1,0,2],[2,1,0,2],[3,1,0,2],
       [0,0,2,1],[1,0,2,1],[2,0,2,1],[3,0,2,1]]

for i in range(n):
  last = now
  now = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
  
  
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          if [i,j,k,l] not in boo:
            now[j][k][l] += last[i][j][k]
            now[j][k][l] %= mod
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += now[i][j][k]
      ans %= mod


print(ans)

Solution (Python):

n = int(input())
mod = 10 ** 9 + 7
now = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
now[3][3][3] = 1

boo = [[0,0,1,2],[1,0,1,2],[2,0,1,2],[3,0,1,2],
       [0,0,1,2],[0,1,1,2],[0,2,1,2],[0,3,1,2],
       [0,1,0,2],[0,1,1,2],[0,1,2,2],[0,1,3,2],
       [0,1,0,2],[1,1,0,2],[2,1,0,2],[3,1,0,2],
       [0,0,2,1],[1,0,2,1],[2,0,2,1],[3,0,2,1]]

for i in range(n):
  last = now
  now = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
  
  
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          if [i,j,k,l] not in boo:
            now[j][k][l] += last[i][j][k]
            now[j][k][l] %= mod
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      ans += now[i][j][k]
      ans %= mod


print(ans)

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

dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
dp[0][3][3][3] = 1
for i in range(N):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                dp[i+1][0][a][b] = (dp[i+1][0][a][b] + dp[i][a][b][c]) % mod
                dp[i+1][3][a][b] = (dp[i+1][3][a][b] + dp[i][a][b][c]) % mod
                if a != 2 or b != 0:
                    dp[i+1][1][a][b] = (dp[i+1][1][a][b] + dp[i][a][b][c]) % mod
                if a == 1 and b == 0:
                    pass
                elif a == 0 and b == 1:
                    pass
                elif b == 1 and c == 0:
                    pass
                elif a == 1 and c == 0:
                    pass
                else:
                    dp[i+1][2][a][b] = (dp[i+1][2][a][b] + dp[i][a][b][c]) % mod

ans = 0
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans = (ans + dp[-1][a][b][c]) % mod
print(ans)

Solution (Python):
n = int(input())
dict = {
3 : 61,
4 : 230 ,
5 : 865 ,
6 : 3247 ,
7 : 12185 ,
8 : 45719 ,
9 : 171531 ,
10 : 643550 ,
11 : 2414454 ,
12 : 9058467 ,
13 : 33985227 ,
14 : 127504505 ,
15 : 478366600 ,
16 : 794717734 ,
17 : 733354121 ,
18 : 261943303 ,
19 : 776803305 ,
20 : 580025381 ,
21 : 51688048 ,
22 : 44657419 ,
23 : 737209731 ,
24 : 604119499 ,
25 : 159693437 ,
26 : 858533109 ,
27 : 639056669 ,
28 : 549054109 ,
29 : 996291083 ,
30 : 531294469 ,
31 : 23314687 ,
32 : 783022045 ,
33 : 855462856 ,
34 : 649970414 ,
35 : 68697295 ,
36 : 409213624 ,
37 : 604356692 ,
38 : 88638656 ,
39 : 978442997 ,
40 : 534833116 ,
41 : 763737161 ,
42 : 785892908 ,
43 : 123883652 ,
44 : 639213333 ,
45 : 181836645 ,
46 : 998121103 ,
47 : 124885216 ,
48 : 501575626 ,
49 : 39816123 ,
50 : 113468411 ,
51 : 799008836 ,
52 : 775465589 ,
53 : 256852905 ,
54 : 664630886 ,
55 : 971550783 ,
56 : 751629411 ,
57 : 51018086 ,
58 : 702530485 ,
59 : 725438992 ,
60 : 696683714 ,
61 : 792638194 ,
62 : 221791721 ,
63 : 149602322 ,
64 : 414054379 ,
65 : 986519078 ,
66 : 981760191 ,
67 : 305799096 ,
68 : 515140586 ,
69 : 406959393 ,
70 : 975058685 ,
71 : 245601370 ,
72 : 324759692 ,
73 : 673385295 ,
74 : 191483611 ,
75 : 570246669 ,
76 : 427196161 ,
77 : 781042769 ,
78 : 569725155 ,
79 : 842176273 ,
80 : 25328739 ,
81 : 847501730 ,
82 : 206282374 ,
83 : 353770801 ,
84 : 323137024 ,
85 : 371653459 ,
86 : 940737264 ,
87 : 123820509 ,
88 : 915711339 ,
89 : 847205021 ,
90 : 252858375 ,
91 : 718889563 ,
92 : 866398347 ,
93 : 738390145 ,
94 : 133009077 ,
95 : 333099663 ,
96 : 170591295 ,
97 : 329869205 ,
98 : 616680192 ,
99 : 597534442 ,
100 : 388130742 
}
print(dict[n])

Solution (Python):
a = ['A', 'G', 'C', 'T']
l = ["GACA","GACC","GACT","AGGC","AGCA","AGCG","AGCC","AGCT","AGTC","ACGA","ACGG","ACGC","ACGT","ATGC"]
dict1_y = {}
dict1_n = {}
dict2_y = {}
dict2_n = {}
t = 3
p = 10**9+7
n = int(input())
for i in a:
    for j in a:
        for k in a:
            s = i + j + k
            dict1_y[s] = 0
            dict1_n[s] = 0
            dict2_y[s] = 0
            dict2_n[s] = 0
for i in a:
    for j in a:
        for k in a:
            s = i + j + k
            if 'AGC' in s:
                dict1_y[s] += 1
            else:
                tem1 = s[0]
                tem2 = s[1]
                new_s = tem2 + tem1 + s[2]
                if 'AGC' in new_s:
                    dict1_y[s] += 1
                else:
                    tem1 = s[1]
                    tem2 = s[2]
                    new_s = s[0] + tem2 + tem1
                    if 'AGC' in new_s:
                        dict1_y[s] += 1
                    else:
                        dict1_n[s] += 1
while t != n:
    for k,v in dict1_y.items():
        for m in a:
            key = m + k[0] + k[1]
            dict2_y[key] += v
    for k,v in dict1_n.items():
        for m in a:
            new_s = m + k
            key = m + k[0] + k[1]
            if new_s in l:
                dict2_y[key] += v
            else:
                dict2_n[key] += v
    for i in a:
        for j in a:
            for k in a:
                s = i + j + k
                dict1_y[s] = dict2_y[s] % p
                dict1_n[s] = dict2_n[s] % p
                dict2_y[s] = 0
                dict2_n[s] = 0
    t += 1
ans = 0
for v in dict1_y.values():
    ans += v % p
print((4**n - ans) % p)

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int):
    mod = 10**9 + 7
    
    
    
    
    

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

    for i in range(2,N+1):
        for j in range(4):
            dp[i][j] += sum(dp[i-1]) 
            dp[i][j] %= mod

        
        
        dp[i][1] -= dp[i-2][0]*1 + dp[i-2][2]*1

        
        
        dp[i][2] -= dp[i-2][0]

        if i >= 3:
            
            dp[i][1] -= dp[i-3][0]*3
            dp[i][2] += dp[i-3][2]

    ans = sum(dp[N]) % mod
    print(ans)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007
n = int(input())
end_a = [0,0,0,16]
end_g = [0,0,0,15]
end_ag = [0,0,0,4]
end_ac = [0,0,0,3]
end_ga = [0,0,0,4]
end_at = [0,0,0,4]
end_aga = [0,0,0,1]
end_agt = [0,0,0,1]
end_agg = [0,0,0,1]
end_atg = [0,0,0,1]
ans = [0,0,0,61]
for i in range(3, n+1):
    end_a.append(ans[i]%mod)
    end_g.append((ans[i] - end_ac[i])%mod)
    end_ag.append(end_a[i]%mod)
    end_ac.append((end_a[i] - end_ga[i])%mod)
    end_ga.append(end_g[i]%mod)
    end_at.append(end_a[i]%mod)
    end_agt.append(end_ag[i]%mod)
    end_agg.append(end_ag[i]%mod)
    end_atg.append(end_at[i]%mod)
    taboo = (end_ag[i] + end_ac[i] + end_ga[i] + end_agt[i] + end_agg[i] + end_atg[i])%mod
    ans.append((taboo*3 + (ans[i]-taboo)*4)%mod)
print(ans[n]%mod)

Solution (Python):
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
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
N=int(input())
dp=[[[[[0 for m in range(4)]for l in range(4)]for k in range(4)]for j 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[3][0][i][j][k]=1
dp[3][0][0][2][1]=0
dp[3][0][0][1][2]=0
dp[3][0][2][0][1]=0

for n in range(4,N+1):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                for a in range(4):
                    for i in range(4):
                        dp[n][b][c][d][a]+=dp[n-1][i][b][c][d]
                        dp[n][b][c][d][a]%=mod
                    dp[n][b][0][2][1]=0
                    dp[n][b][2][0][1]=0
                    dp[n][b][0][1][2]=0
                    dp[n][0][c][2][1]=0
                    dp[n][0][2][d][1]=0
ans=0
for a in range(4):
    for b in range(4):
        for c in range(4):
            for d in range(4):
                ans+=dp[N][a][b][c][d]
print(ans%mod)

Solution (Python):
n=int(input())
m=[{}for i in range(n+1)]
w=10**9+7
def f(s):
    for i in range(4):
        t=list(s)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>0:
            return False
    return True
def a(p,q):
    if q in m[p]:
        return m[p][q]
    if p==n:
        return 1
    r=0
    for i in "AGCT":
        if f(q+i):
            r=(r+a(p+1,q[1:]+i))%w
    m[p][q]=r
    return r
print(a(0,"WHY"))

Solution (Python):


import itertools, copy

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

if N == 3:
    print(4**3-3)
    exit()


out_letters_4 = set()
for x in ["A", "C", "G", "T"]:
    out_letters_4.add("A" + x + "GC")
    out_letters_4.add("AG" + x + "C")
    for y in ["AGC", "GAC", "ACG"]:
        out_letters_4.add(x + y)
        out_letters_4.add(y + x)


tmp = list(itertools.product(["A", "C", "G", "T"], repeat = 4))
all_letters_4 = set()
for x in tmp:
    tmp2 = ""
    for y in x:
        tmp2 += y
    all_letters_4.add(tmp2)

possible_letters_4 = all_letters_4 - out_letters_4


trans_letters_4_dict = dict.fromkeys(possible_letters_4, -1)
for key in trans_letters_4_dict.keys():
    for x in ["A", "C", "G", "T"]:
        tmp = (key + x)[1:]
        if tmp in trans_letters_4_dict.keys():
            if trans_letters_4_dict[key] == -1:
                trans_letters_4_dict[key] = [tmp]
            else:
                trans_letters_4_dict[key].append(tmp)

n_pattern = dict.fromkeys(possible_letters_4, 1)

for _ in range(N-4):
    next_n_pattern = dict.fromkeys(possible_letters_4, 0)
    for former_key in possible_letters_4:
        for to_key in trans_letters_4_dict[former_key]:
            next_n_pattern[to_key] += n_pattern[former_key]
    n_pattern = copy.deepcopy(next_n_pattern)

print(sum(n_pattern.values()) % MOD)

Solution (Python):


N = int(input())
MOD = 1e+9+7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			dp[3][c1][c2][c3] = 1

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

for n in range(4, N+1):
	for c1 in range(4):
		for c2 in range(4):
			for c3 in range(4):
				for a in range(4):
				
					if a==2 and c2 == 0 and c3 == 1:
						continue
					if a==2 and c2 == 1 and c3 == 0:
						continue
					if a==2 and c1 == 0 and c3 == 1:
						continue
					if a==2 and c1 == 0 and c2 == 1:
						continue
					if a==1 and c2 == 0 and c3 == 2:
						continue
				
					dp[n][c2][c3][a] += dp[n-1][c1][c2][c3]
					dp[n][c2][c3][a]  = int(dp[n][c2][c3][a]%MOD)
cnt = 0
mod = 1e+9+7
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			cnt += dp[N][c1][c2][c3]
cnt = int(cnt%mod)
print(cnt)

Solution (Python):

n = int(input())
l=[{} for i in range(2)]
mod = 10**9+7

def judge(s):
  t=list(s)
  if ''.join(t).find('AGC') != -1:
    return False
  t[0],t[1]=t[1],t[0]
  if ''.join(t).find('AGC') != -1:
    return False
  t[0],t[1]=t[1],t[0]
  t[1],t[2]=t[2],t[1]
  if ''.join(t).find('AGC') != -1:
    return False
  t[1],t[2]=t[2],t[1]
  t[2],t[3]=t[3],t[2]
  if ''.join(t).find('AGC') != -1:
    return False
  return True

l[1]['XXX']=1

for i in range(n):
  l[i%2].clear()
  for s in l[(i+1)%2]:
    for c in 'ACGT':
      l[i%2][s[1:]+c] = 0

  t = 0
  for s in l[(i+1)%2]:
    for c in 'ACGT':
      if judge(s+c):
        l[i%2][s[1:]+c] = (l[i%2][s[1:]+c]+l[(i+1)%2][s]) % mod
        t = (t + l[(i+1)%2][s]) % mod
print(t)

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

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

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

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

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

answer = dfs(0, 'TTT')
print(answer)

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

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

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

@lru_cache(maxsize=None)
def search(n, prev):
    if n == 0:
        return 1

    ret = 0
    for s in ['A', 'G', 'C', 'T']:
        t = (prev + s)[1:]
        if isOk(t):
            ret += search(n - 1, t)
            ret %= MOD

    return ret

print(search(N, 'ZZZZ'))

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
dp = [{} for i in range(N+4)]

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).find('AGC') != -1:
            return False
    return True

def dfs(i, last3):
    if last3 in dp[i]:
        return dp[i][last3]
    if i == N:
        return 1
    cou = int(0)
    for s in "ACGT":
        if ok(last3+s):
            cou = (cou + dfs(i+1, last3[1:]+s)) % mod

    dp[i][last3] = cou
    return cou

ans = dfs(0,"TTT")
print(ans)

Solution (Python):
N = int(input())
MOD = 1000000007
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
dp[0][3][3][3] = 1
for n in range(N):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (dp[n][i][j][k] == 0): continue
                for a in range(4):
                    if (j==0 and k==1 and a==2): continue
                    if (j==1 and k==0 and a==2): continue
                    if (j==0 and k==2 and a==1): continue
                    if (i==0 and k==1 and a==2): continue
                    if (i==0 and j==1 and a==2): continue
                    dp[n+1][j][k][a] += dp[n][i][j][k]
                    dp[n+1][j][k][a] %= 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 %= MOD
print(ans)