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):
import numpy as np
import sys

MOD = 10**9 + 7
N=int(input())
dp = [{} for i in range(N+1)]
dp[0] = {"XXX":1}


def ok(l):
    r = True
    r = r and not "AGC" in l
    r = r and not "AGC" in l[1]+l[0]+l[2]+l[3]
    r = r and not "AGC" in l[0]+l[2]+l[1]+l[3]
    r = r and not "AGC" in l[0]+l[1]+l[3]+l[2]
    return r


for i in range(N):
    for key in dp[i]:
        for c in "ATCG":
            s = key+c
            if ok(s):
                new_key = s[1:4]
                if not new_key in dp[i+1]:
                    dp[i+1][new_key] = dp[i][key]
                else:
                    dp[i+1][new_key] += dp[i][key]

cnt = 0
for k in dp[N]:
    cnt += dp[N][k]


print(cnt % MOD)

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

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

def ok(l4):
  if (l4[0:3] in ['AGC', 'GAC', 'ACG'] or
      l4[1:4] in ['AGC', 'GAC', 'ACG'] or
      l4[0:1] + l4[2:4] == 'AGC' or
      l4[0:2] + l4[3:4] == 'AGC'):
    return False
  else:
    return True

for c1 in C:
  for c2 in C:
    for c3 in C:
      l4 = 'X' + c1 + c2 + c3
      if ok(l4):
        dp[3][l4] = 1
      else:
        dp[3][l4] = 0

for i in range(4, N+1):
  for l4 in dp[i-1].keys():
    for c in C:
      next_l4 = l4[1:4] + c
      if next_l4 not in dp[i]:
        dp[i][next_l4] = 0
      if ok(next_l4):
        dp[i][next_l4] = (dp[i][next_l4] + dp[i-1][l4]) % MOD

ans = 0
for count in dp[N].values():
  ans = (ans + count) % 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 c3 in range(4)] for c2 in range(4)] for c1 in range(4)] for l in range(N + 1)]
dp[0][3][3][3] = 1
for l in range(N):  
    for c1 in range(4):  
        for c2 in range(4):  
            for c3 in range(4):  

                if(0 == dp[l][c1][c2][c3]):    continue
                for a in range(4):
                    
                    if((a == 2) & (c1 == 1) & (c2 == 0)):  continue
                    if((a == 2) & (c1 == 0) & (c2 == 1)):  continue
                    if((a == 1) & (c1 == 2) & (c2 == 0)):  continue
                    if((a == 2) & (c1 == 1) & (c3 == 0)):  continue
                    if((a == 2) & (c2 == 1) & (c3 == 0)):  continue

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

                    dp[l][c1][c2][c3] %= 10 ** 9 + 7

ans = 0
for c1 in range(4):  
    for c2 in range(4):  
        for c3 in range(4):  
            ans += dp[N][c1][c2][c3]
            ans %= 10 ** 9 + 7

print(str(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, '***'))

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

    ans = editorial(N)
    ans1 = editorial_dp(N)

    assert ans == ans1
    print(ans)


def editorial(N):
    MOD = 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 += dfs(cur + 1, last3[1:] + c)
                ret %= MOD
        memo[cur][last3] = ret

        return ret

    
    ans = dfs(0, 'TTT')
    return ans


def editorial_dp(N):
    """
    AGC
    ACG
    GAC
    ----
    追加+swap
    AG.C
    A.GC
    """
    import numpy as np
    from itertools import product

    T, A, G, C = range(4)
    MOD = 10 ** 9 + 7
    dp = np.zeros((N+1, 4, 4, 4), dtype=int)
    
    dp[0, 0, 0, 0] = 1
    ng_pattern = (A, G, C)

    for i in range(N):
        for c1, c2, c3 in product(range(4), repeat=3):
            if dp[i, c1, c2, c3] == 0:
                continue

            for c4 in range(4):
                patterns = [
                    
                    (c2, c3, c4),
                    (c2, c4, c3),
                    (c3, c2, c4),
                    
                    (c1, c2, c4),
                    (c1, c3, c4),
                ]
                ng = any(ng_pattern == p for p in patterns)
                if ng:
                    continue

                dp[i+1, c2, c3, c4] += dp[i, c1, c2, c3]
                dp[i+1, c2, c3, c4] %= MOD

    ans = 0
    for c1, c2, c3 in product(range(4), repeat=3):
        ans += dp[N, c1, c2, c3]
        ans %= MOD

    return ans


def WA(N):
    """
    3 <= N <= 100
    4種類の文字: ACGT
    4^N 通りの文字列が存在する
    隣接文字2つを1回入れかることができる
    違反: AGC
    違反: 入力例1より
        ACG
        GAC

    2文字までは違反なし
    3文字では3つ違反, 上記の通り
        64-3 = 61
    4文字
        4文字目追加なので61 * 4
        3文字目の時点で3つで終わるパターンがある
        次に 下記パターンの文字が追加されるとNG
            AG C
            AC G
            GA C

        3文字のときに終わるパターンの構成
            AG: [.]AG NGなし    ACGT 4
            AC: [G]AC NGより    AC T 3
            GA: [.]GA NGなし    ACGT 4

        AG: 構成4 * OK:4-1
        AC: 構成3 * OK:4-1
        GA: 構成4 * OK:4-1
            61 + (61 * 4 - [4+3+4] * 1)

        pattern に周期がありそう
        全パターンから引くので、逆元を使いそう
    """
    ans = 61
    ag_ac_ga = [4, 3, 4]
    if N == 3:
        return ans

    MOD = 10 ** 9 + 7
    for i in range(4, N+1):
        ag_ac_ga = [x * 3 for x in ag_ac_ga]
        print(ans + ans * i)
        print(sum(ag_ac_ga))
        ans += ans * i - sum(ag_ac_ga) * 3
        

    ans %= MOD

    aaa()
    return ans


def aaa():
    ans = []
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    x = "".join(map(str, [i, j, k, l]))
                    
                    
                    y = any(z in x for z in ("021", "012", "201"))
                    ans.append((x, y))

    print(*ans, sep="\n")
    print(sum(x[1] for x in ans))
    print(len(ans))


if __name__ == "__main__":
    main()

Solution (Python):
import itertools

N = int(input())

mod = 10 ** 9 + 7

dp = [[[[0 for i in range(0,4)] for j in range(0,4)] for k in range(0, 4)] for n in range(0, N + 1)]

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













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

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

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


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

print(res % mod)

Solution (Python):
import itertools
def memo_rec(N):
    if N == 3:
        return 61
    if N == 4:
        return 230
    L = "ATGC"
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(s, k):
        if s.count("AGC"):
            return 0
        for i in range(3):
            t1, t2 = s[i], s[i + 1]
            if (s[:i] + t2 + t1 + s[i+2:]).count("AGC"):
                return 0
        if k == 0:
            return 1
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(str(x + s[:3]), k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 4):
        t = ''
        for x in s:
            t += x
        ret = (ret + rec(t, N - 4)) % MOD
    return ret

N = int(input())
print(memo_rec(N))

Solution (Python):



from math import factorial
import numpy as np
from itertools import product

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


def main():
  N = int(input())
  M = 10**9 + 7
  DP = np.ones((4, 4, 4), dtype=np.int)
  g2i = {g:i for i,g in enumerate(list('ATGC'))}
  DP[tuple([g2i[g] for g in 'AGC'])] = 0
  DP[tuple([g2i[g] for g in 'GAC'])] = 0
  DP[tuple([g2i[g] for g in 'ACG'])] = 0
  for i in range(N-3):
    _DP = np.zeros((4, 4, 4), dtype=np.int)
    for last3 in [''.join(x) for x in product(*(['ATGC']*3))]:
      for c in 'ATGC':
        if check(last3+c):
          
          _DP[tuple([g2i[g] for g in last3[1:]+c])] += DP[tuple([g2i[g] for g in last3])]
          _DP[tuple([g2i[g] for g in last3[1:]+c])] %= M
    DP = _DP
  
  print(np.sum(DP) % M)

if __name__=='__main__':
  main()

Solution (Python):
def ok(s):
    for i in range(len(s)):
        s_list = list(s)
        if i < len(s)-1:
            s_list[i], s_list[i+1] = s_list[i+1], s_list[i]
        if ''.join(s_list).find("AGC") != -1:
            return False
    return True


n = int(input())
table = [{} for i in range(n+1)]
table[0][''] = 1

for i in range(n):
    for s in table[i]:
        for c in 'ATGC':
            if ok(s[-3:] + c):
                if s[-2:]+c in table[i+1]:
                    table[i+1][s[-2:]+c] += table[i][s]
                else:
                    table[i+1][s[-2:]+c] = table[i][s]

print(sum(table[n].values()) % (10 ** 9 + 7))

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

    
    
    
    dp = [[[[0 for k in range(4)] for k in range(4)] for j in range(4)] for i in range(N + 1)]
    
    
    dp[0][3][3][3] = 1

    def digit2acgt(a, b, c, d):
        
        a, b, c, d = map(lambda x: 'ACGT'[x], (a, b, c, d))
        return ('*' + b + c + d, a + '*' + c + d, a + b + '*' + d)

    for k in range(N):
        for c0, c1, c2, c3 in product(range(4), repeat=4):
            for s in digit2acgt(c0, c1, c2, c3):
                
                if s in ('*AGC', '*GAC', '*ACG', 'A*GC', 'AG*C'):
                    break
            else:
                
                
                dp[k + 1][c1][c2][c3] += dp[k][c0][c1][c2]
                dp[k + 1][c1][c2][c3] %= MOD

    ans = 0
    for c0, c1, c2 in product(range(4), repeat=3):
        ans += dp[N][c0][c1][c2]
        ans %= MOD
    return ans

N = int(input())
print(d_we_like_agc(N))

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

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


for num in range(1):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for add in range(4):
          if c2 == 0 and c1 == 1 and add ==2:
            continue
          if c2 == 0 and c1 == 2 and add ==1:
            continue
          if c2 == 1 and c1 == 0 and add ==2:
            continue  
          if c3 == 0 and c2 == 1 and add ==2:
            continue
          if c3 == 0 and c1 == 1 and add ==2:
            continue
          dp[3][add][c1][c2] = 1

for num in range(1,n):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for add in range(4):
          if c2 == 0 and c1 == 1 and add ==2:
            continue
          if c2 == 0 and c1 == 2 and add ==1:
            continue
          if c2 == 1 and c1 == 0 and add ==2:
            continue  
          if c3 == 0 and c2 == 1 and add ==2:
            continue
          if c3 == 0 and c1 == 1 and add ==2:
            continue
          dp[num+1][add][c1][c2] += dp[num][c1][c2][c3]
          dp[num+1][add][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
if n ==1:
  print(4)
elif n ==2:
  print(16)
else:
  print(ans)

Solution (Python):
import re
N = int(input())
memo_dict = [{} for i in range(N+1)]
def ok(last4):
    if re.match(r".*AGC|.*ACG|A.GC|AG.C|.*GAC", last4):
        return True
    else:
        return False

def dfs(ind, last3):
    if last3 in memo_dict[ind]:
        return memo_dict[ind][last3]
    if ind == N:
        return 1
    cnt = 0
    for c in "ATGC":
        if not ok(last3 + c):
            cnt += dfs(ind + 1, last3[1:] + c)
            cnt %= (1e9+7)
    memo_dict[ind][last3] = cnt
    return cnt
print(int(dfs(0,"TTT")))

Solution (Python):
def compute():
  from sys import stdin
  N = int(stdin.readline().strip())
  MOD = int(1e9)+7

  dp = {}
  prohibited = ('AGC', 'ACG', 'GAC')

  def flt(a,b,c,d):
    if (b is None) or (c is None) or (d is None):
      return True
    if (b+c+d) in prohibited:
      return False
    if (a is not None) and (((a+c+d)=='AGC') or ((a+b+d)=='AGC')):
      return False
    return True

  def f(prev3, prev2, prev1, n):
    if n==0:
      return 1

    k = (prev3, prev2, prev1, n)
    if k in dp:
      return dp[k]

    nexlis = ('A', 'C', 'G', 'T')
    ret = sum(map(
      lambda nex: f(prev2, prev1, nex, n-1),
      filter(
        lambda nex: flt(prev3, prev2, prev1, nex),
        nexlis
      )
    )) % MOD

    dp[k] = ret
    return ret

  print( f(None, None, None, N) )


if __name__ == "__main__":
  compute()

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 collections import Counter
from itertools import product

def main():
    N = II()
    dp = Counter()
    dp['TTT'] += 1
    for _ in range(N):
        pre = dp
        dp = Counter()
        for p1, p2, p3, cur in product('ACGT', repeat=4):
            if p2 + p1 + cur in ['AGC', 'GAC', 'ACG']:
                continue
            if p3 + p1 + cur == 'AGC':
                continue
            if p3 + p2 + cur == 'AGC':
                continue
            new = p2 + p1 + cur
            old = p3 + p2 + p1
            dp[new] = (dp[new] + pre[old]) % MOD
    ans = sum(dp.values())

    return ans % MOD

print(main())

Solution (Python):
from sys import stdin


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


mod = 10**9 + 7


N = int(stdin.readline().rstrip())


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


"""

AGC(012)
GAC(102)
ACG(021)
A?GC(0?12)
AG?C(01?2)


c1: 後ろから3番目の文字
c2: 後ろから2番目の文字
c3: 後ろから1番目の文字
a: 追加する文字列
"""

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

for i in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for a in range(4):
                    
                    if c2 == A and c3 == G and a == C: continue 
                    if c2 == G and c3 == A and a == C: continue 
                    if c2 == A and c3 == C and a == G: continue 
                    if c1 == A and c3 == G and a == C: continue 
                    if c1 == A and c2 == G and a == C: continue 
                    
                    
                    
                    
                    dp[i+1][c2][c3][a] += dp[i][c1][c2][c3]
                    dp[i+1][c2][c3][a] %= 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):
import sys
from collections import deque
import copy
import math
import re

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    dp = [[[[0L for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N + 1)]
    dp[0][3][3][3] = 1
    for i in range(N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    for x in range(4):
                        if x == 2 and c2 == 1 and c3 == 0:
                            continue
                        if x == 2 and c1 == 1 and c3 == 0:
                            continue
                        if x == 2 and c2 == 0 and c1 == 1:
                            continue
                        if x == 2 and c2 == 1 and c1 == 0:
                            continue
                        if x == 1 and c2 == 0 and c1 == 2:
                            continue
                        dp[i + 1][c2][c1][x] = (dp[i + 1][c2][c1][x] + dp[i][c3][c2][c1] ) % 1000000007L
    count = 0L
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                    count = (count + dp[N][c1][c2][c3]) % 1000000007L

    print count

















if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip())
MOD =10**9+7
MEMO = [{} for _ in range(N+1)]
ACGT = "ACGT"
ACG = ["ACG","AGC","CAG","ATCG","ACTG","ACCG"]

def acg_check(last4):
  for acg in ACG:
    if acg in last4:
      return False
  return True

def func(length, last3):
  if last3 in MEMO[length]:
    return MEMO[length][last3]
  if length == N:
    return 1

  ans = 0
  for c in ACGT:
    if len(last3)==3:
      if acg_check(last3+c):
        ans += func(length+1,last3[1:]+c)%MOD
    else:
      if acg_check(last3+c):
        ans += func(length+1,last3+c)%MOD
  MEMO[length][last3] = ans
  return ans

print(func(0,"")%MOD)

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 main():
    N = II()
    A, G, C, T = range(4)
    def code(c0, c1, c2):
        return c0 + 4 * c1 + 16 * c2
    dp = [0] * 64
    dp[code(T, T, T)] = 1
    for _ in range(N):
        pre = dp
        dp = [0] * 64
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) in [(A, G, C), (A, C, G), (G, A, C)]:
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                dp[code(cur, p1, p2)] += pre[code(p1, p2, p3)]
                dp[code(cur, p1, p2)] %= MOD
    ans = sum(dp)

    return ans % MOD

print(main())

Solution (Python):
N = int(input())
MOD = 1000000007
chars = ['A', 'C', 'G', 'T']

def seq_gen():
    return ((c1, c2, c3) for c3 in chars for c2 in chars for c1 in chars)

tbl = {}
for i in range(N+1):
    for c1, c2, c3 in seq_gen():
        tbl[(i, c1, c2, c3)] = 0

tbl[(0,'T','T','T')] = 1

for i in range(N):
    for c1, c2, c3 in seq_gen():
        if tbl[(i, c1, c2, c3)] == 0:
            continue
        for a in chars:
            ng_cond =   (a + c1 + c2 == 'AGC' or
                        a + c1 + c2 == 'ACG' or
                        a + c1 + c2 == 'GAC' or
                        a + c2 + c3 == 'AGC' or
                        a + c1 + c3 == 'AGC')
            if not ng_cond:
                tbl[(i+1, a, c1, c2)] += tbl[(i, c1, c2, c3)]
                tbl[(i+1, a, c1, c2)] %= MOD

ans = 0
for c1, c2, c3 in seq_gen():
    ans += tbl[(N, c1, c2, c3)]
    ans %= MOD

print(ans)

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 main():
    N = II()
    A, G, C, T = range(4)
    def code(c0, c1, c2):
        return c0 + 4 * c1 + 16 * c2
    dp = [0] * 64
    dp[code(T, T, T)] = 1
    for _ in range(N):
        tmp = [0] * 64
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) == (A, G, C):
                    continue
                if (p2, p1, cur) == (A, C, G):
                    continue
                if (p2, p1, cur) == (G, A, C):
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                tmp[code(cur, p1, p2)] += dp[code(p1, p2, p3)]
                tmp[code(cur, p1, p2)] %= MOD
        dp = tmp
    ans = sum(dp)

    return ans % MOD

print(main())

Solution (Python):
N, MOD = int(input()), 10 ** 9 + 7
dp = [[[[0 for k in range(4)] for k in range(4)] for j in range(4)] for i in range(101)]
' 長さ0の文字列は1である。        '
' 0,1,2に関する制約しかないので、 '
' Sは、333Sと考えても問題がない。 '
dp[0][3][3][3] = 1

for length in range(N):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        if dp[length][c1][c2][c3] == 0: continue
        for c4 in range(4):
          ' ダメな5つの条件をカットする'
          if   True  and c2 == 0 and c3 == 1 and c4 == 2: continue
          if   True  and c2 == 1 and c3 == 0 and c4 == 2: continue
          if   True  and c2 == 0 and c3 == 2 and c4 == 1: continue
          if c1 == 0 and c2 == 1 and   True  and c4 == 2: continue
          if c1 == 0 and   True  and c3 == 1 and c4 == 2: continue

          ' ダメな条件を抜けたら、c4を足した文字列が作れる '
          ' S     = ...... c1 c2 c3                        '
          ' nextS = ...... c2 c3 c4                        '
          dp[length + 1][c2][c3][c4] += dp[length][c1][c2][c3]
          dp[length + 1][c2][c3][c4] %= 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=102
chars=['A','T','C','G']
mo=10**9+7
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)

dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1

t=1+n
for i in range(4,t):
    for ch in chars:
        for p in dp[i-1].keys():
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo

if n==3:
    ans=61
    print(ans)
else:
    print(cnt[n])

Solution (Python):

n=int(input())
m=102
chars=['A','T','C','G']
mo=10**9+7
d3=set()
d4=set()
for i in chars:
    for j in chars:
        for k in chars:
            d3.add(i+j+k)
            for l in chars:
                d4.add(i+j+k+l)
        
kinsoku4=set()
kinsoku3=['AGC','ACG','GAC']

for y in chars:
    kinsoku4.add('AG'+y+'C')
    kinsoku4.add('A'+y+'GC')
    for z in kinsoku3:
        kinsoku4.add(y+z)
        kinsoku4.add(z+y)


dp=[dict() for i in range(m)]
cnt=[0]*m
for i in d4:
    if i not in kinsoku4:
        dp[4][i]=1
    

t=101
for i in range(4,t):
    for ch in chars:
        for p in dp[i-1].keys():
            if p[1:4]+ch not in kinsoku4:
                if p[1:4]+ch in dp[i]:
                    dp[i][p[1:4]+ch]+=dp[i-1][p]%mo
                else:
                    dp[i][p[1:4]+ch]=dp[i-1][p]%mo
for i in range(t):
    for x in d4:
        if x not in kinsoku4 and x in dp[i]:
            cnt[i]+=dp[i][x]%mo
    cnt[i]%=mo





    

if n==3:
    ans=61
    print(ans)
else:
    print(cnt[n])

Solution (Python):

from itertools import product
MOD = 10**9 + 7
N = int(input())

A, G, C, T = range(4)
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
      for _ in range(N + 1)]
dp[0][T][T][T] = 1
for k in range(N):
    for c0, c1, c2, c3 in product(range(4), repeat=4):
        if c1 == A and c2 == G and c3 == C: continue
        if c1 == G and c2 == A and c3 == C: continue
        if c1 == A and c2 == C and c3 == G: continue
        if c0 == A and c2 == G and c3 == C: continue
        if c0 == A and c1 == G and c3 == C: continue
        dp[k + 1][c1][c2][c3] += dp[k][c0][c1][c2]
        dp[k + 1][c1][c2][c3] %= MOD

ans = 0
for c0, c1, c2 in product(range(4), repeat=3):
    ans += dp[N][c0][c1][c2]
    ans %= MOD
print(ans)

Solution (Python):

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

sys.setrecursionlimit(100000)


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap

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

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

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

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


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

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

    for _ in range(N-4):
        dp_ = Counter()
        for k, v in dp.items():
            for c in 'agct':
                s = k + c
                s = s[1:]
                if s in dp:
                    dp_[s] = m.add(v, dp_[s])
        dp = dp_
    
    return reduce(m.add, dp.values())


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


if __name__ == '__main__':
    main()

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

t = [0] * (n + 1)
a = [0] * (n + 1)
g = [0] * (n + 1)
ac = [0] * (n + 1)

t[0] = 1
t[1] = 4
t[2] = 16
a[1] = 1
a[2] = 4
g[1] = 1
g[2] = 4
ac[2] = 1

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

print(t[n] % (10**9 + 7))