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.



Sample input:
3


Sample output:
61

Submission status: Runtime Error

Solution code:
n = int(input())
MOD = 10 ** 9 + 7
# dp[i][i-1][i-2][i-3][i-4]
dp = [[[[[0] * (4) for _ in range(4)] for i in range(4)] for i in range(4)] for i in range(n + 1)]

to = {0:"A", 1:"C", 2:"G", 3:"T"}
for i1 in range(4):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                if "AGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue
                if "ACG" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "GAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AAGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "ACGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "ATGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGCC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                if "AGTC" in to[i1] + to[i2] + to[i3] + to[i4]:
                    continue 
                dp[4][i1][i2][i3][i4] = 1

for i in range(4, n):
    for i1 in range(4):
        for i2 in range(4):
            for i3 in range(4):
                for i4 in range(4):
                    if "AGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue
                    if "ACG" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "GAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AAGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "ACGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "ATGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGAC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGCC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGGC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    if "AGTC" in to[i1] + to[i2] + to[i3] + to[i4]:
                        continue 
                    for j in range(4):
                        dp[i + 1][i1][i2][i3][i4] += dp[i][i2][i3][i4][j]
                        dp[i + 1][i1][i2][i3][i4] %= MOD

if n == 3:
    print(61)
    exit()
ans = 0
for i1 in range(4):
    for i2 in range(4):
        for i3 in range(4):
            for i4 in range(4):
                ans += dp[-1][i1][i2][i3][i4]
                ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
###########
import numpy as np
n,k = list(map(int, input().split()))
p = list(map(int, input().split()))

pk = np.array([])
ansum = np.array([])
for i,name  in enumerate(p):
    pk = np.append(pk, (name+1)/2)
    if i >= 2:
        ansum = np.append(ansum, np.sum(pk[-3:]))

print(np.max(ansum))

Submission status: Runtime Error

Solution code:
n=int(input())
alph=["A","C","G","T"]
a=[alph[i]+alph[j]+alph[k] for i in range(4) for j in range(4) for k in range(4)]
d1={l:0 for l in a}
for i in d1:
    if i!="AGC" and i!="ACG" and i!="GAC":
        d1[i]=1
d2={l:0 for l in a}
for i in range(n-3):
    for j in d1:
        next=[j+alph[k] for k in range(4)]
        for k in range(4):
            l=next[k]
            check1=l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC"
            check2=l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC"
            if (not check1) and (not check2)
                d2[l[1:]]+=d1[j]
    for j in d1:
        d1[j]=d2[j]%1000000007
        d2[j]=0
print(sum(d1.values())%1000000007)

Submission status: Runtime Error

Solution code:
ANS=[0, 0, 0, 61, 230, 865, 3247, 12185, 45719, 171531]
print(ANS[int(input())])

Submission status: Runtime Error

Solution code:
n=int(input())
mod=10**9+7
if n==3:
    print(61)
    exit()
zt=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in zt:
        for k in list('AGCT'):
            tmp.append(j+k)
    zt=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
    ng.add('ACG'+i)
    ng.add('GAC'+i)
    ng.add(i+'ACG')
    ng.add(i+'GAC')
z=set([])
for j in zt:
    if not j in ng:
        z.add(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   # if not z[i] in ng:
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            #if not z[k] in ng:
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
cs = 'ATGC'
ng = [
  'AGC',
  'GAC',
  'ACG'
]
mod = 10**9 + 7
d = defaultdict(int)
for c1 in cs:
  for c2 in cs:
    for c3 in cs:
      s = c1 + c2 + c3
      if s not in ng:
        d[s] += 1
for i in range(3, n):
  nd = defaultdict(int)
  for key in d.keys:
    for c in cs:
      cn = key[1:2] + c
      if cn not in ng:
        nd[cn] = (nd[cn] + d[key]) % mod
  d = nd
print(sum([d[key] for key in d]) % mod)

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
N = int(input())

C = 10**9+7
n = 5
L = [0 for i in range(N+1)]
X = [0 for i in range(N+1)]
Y = [0 for i in range(N+1)]
Z = [0 for i in range(N+1)]
W = [0 for i in range(N+1)]
G = [0 for i in range(N+1)]
L[3] = 61
L[4] = 230
X[3] = 3
X[4] = 12
Y[3] = 4
Y[4] = 16
Z[3] = 4
Z[4] = 15
W[3] = 3
W[4] = 12
W[5] = 48
G[3] = 15
G[4] = 58
while n <= N:
    L[n] = 4*L[n-1] - (X[n-1]+Y[n-1]+Z[n-1]+W[n-1])
    G[n] = L[n-1]-X[n-1]
    X[n] = L[n-2]-G[n-2]
    Y[n] = L[n-2]
    Z[n] = L[n-2]-X[n-2]
    if n > 5:
        W[n] = L[n-3]*3
    n += 1

print(L[N]%C)

Submission status: Runtime Error

Solution code:
oteage

Submission status: Runtime Error

Solution code:
#include<cstdio>

const int A = 1e9 + 7;
int n;
int dp[98][64];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
               dp[0][16 * i + 4 * j + k] = 1;
            }
        }
    }
    dp[0][9]--;
    dp[0][49]--;
    dp[0][6]--;
    for (int i = 1; i < n - 2; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                for (int l = 0; l < 4; l++) {
                    for (int m = 0; m < 4; m++) {
                        if (16 * j + 4 * l + m == 9) continue;
                        if (16 * l + 4 * k + m == 9) continue;
                        if (16 * j + 4 * k + m == 9) continue;
                        if (16 * k + 4 * m + l == 9) continue;
                        if (16 * k + 4 * l + m == 9) continue;
                        dp[i][16 * k + 4 * l + m] += dp[i - 1][16 * j + 4 * k + l];
                        dp[i][16 * k + 4 * l + m] %= A;
                    }
                }
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < 64; i++) {
        sum += dp[n - 3][i];
        sum %= A;
    }
    printf("%d\n", sum);
    return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    n = I()


    def ok(last, c):
        last_plus = last + c
        if 'agc' in last_plus:
            return 0
        for i in range(len(last_plus)-1):
            tmp = list(last_plus)
            tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
            if 'agc' in ''.join(tmp):
                return 0
        return 1



    D = [defaultdict(int) for _ in range(n+1)]
    D[0][''] = 1


    for i in range(n):
        for k, v in D[i].items():
            for c in 'acgt':
                if ok(k, c):
                    D[i+1][(k + c)[-3:]] += v
                    D[i + 1][(k + c)[-3:]] %= mod
    return sum(D[n].values()) % mod





print(main())






main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys
import re


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():


    n = I()


    def ok(last, c):
        last_plus = last + c
        if 'agc' in last_plus:
            return 0
        for i in range(len(last_plus)-1):
            tmp = list(last_plus)
            tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
            if 'agc' in ''.join(tmp):
                return 0
        return 1



    D = [defaultdict(int) for _ in range(n+1)]
    D[0][''] = 1


    for i in range(n):
        for k, v in D[i].items():
            for c in 'acgt':
                if ok(k, c):
                    D[i+1][(k + c)[-3:]] += v
                    D[i + 1][(k + c)[-3:]] %= mod
    return sum(D[n].values()) % mod





print(main())



main()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
S = input()

count = [0] * N
i = 0
while i in range(N-1):
    
    if S[i:i+2] == "AC":
        count[i] = 1
        i+= 2
        
    else:
        i += 1

for q in range(Q):
    l,r = map(int, input().split())
    print(sum(count[l-1:r-1]))

Submission status: Runtime Error

Solution code:
n, MOD = int(input()), 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], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            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 "AGCT":
        if ok(last3 + c):
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Submission status: Runtime Error

Solution code:
n, MOD = int(input()), 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], t[i-1] = t[i-1], t[i]
        if "".join(t).count("AGC") != 0:
            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 "AGCT":
        if ok(last3) + c:
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
A_1 = np.zeros((4,4), dtype='int64')
A_2 = np.ones((4,4), dtype='int64')
B = np.ones((4,4), dtype='int64')
for _ in range(n-2):
    A_3 = (B@A_2).T
    A_3 %= 10**9+7
    A_3[2,1] -= A_2[0,2]+A_1[0,2]+A_1[0,3]
    A_3[1,2] -= A_2[0,1]
    A_3[0,1] -= A_2[2,0]
    A_3[3,1] -= A_1[0,2]
    A_1, A_2 = A_2, A_3
print(np.sum(A_3)%(10**9+7))

Submission status: Runtime Error

Solution code:
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":
        ret=(ret+dfs(cur+1,last3[1:]+c))%mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,"TTT"))

Submission status: Runtime Error

Solution code:
import copy

def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]

print(sum(dp_list)%mod)

Submission status: Runtime Error

Solution code:

def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]

print(sum(dp_list)%mod)

Submission status: Runtime Error

Solution code:
XAA = 1
XAT = 1
XAG = 1
XAC = 1
XTA = 1
XTT = 1
XTG = 1
XTC = 1
XGA = 1
XGT = 1
XGG = 1
XGC = 1
XCA = 1
XCT = 1
XCG = 1
XCC = 1
m = 1000000007

for i in range(N-2):
  XAA, XAT, XAG, XAC, XTA, XTT, XTG, XTC, XGA, XGT, XGG, XGC, XCA, XCT, XCG, XCC = (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XGA + XCA)%m, (XAA + XTA + XCA)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAT + XTT + XGT + XCT)%m, (XAG + XTG + XGG)%m, (XAG + XTG + XGG + XCG)%m, (XAG + XTG + XGG + XCG)%m, (XTG + XGG + XCG)%m, (XAC + XTC + XGC + XCC)%m, (XAC + XTC + XGC + XCC)%m, (XTC + XGC + XCC)%m, (XAC + XTC + XGC + XCC)%m

print((XAA+XAT+XAG+XAC+XTA+XTT+XTG+XTC+XGA+XGT+XGG+XGC+XCA+XCT+XCG+XCC)%m)

Submission status: Runtime Error

Solution code:
n=int(input())
mod=10**9+7
l=['A','C','G','T']
NG=['AGC','GAC','ACG']
NG2=['AAGC','ACGC','AGGC','ATGC','AGAC','AGCC','AGTC']
L=[]
for i1 in range(4):
  for i2 in range(4):
    for i3 in range(4):
      for i4 in range(4):
        L.append(l[i1]+l[i2]+l[i3]+l[i4])
dp=[[0 for i in range(256)] for j in range(n+1)]
for i in range(256):
  if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
    dp[4][i]=0
  else:
    dp[4][i]=1
for j in range(5,n+1):
  for i in range(256):
    if L[i][1:4] in NG or L[i][0:3] in NG or L[i] in NG2:
      dp[j][i]=0
    else:
      for i2 in range(256):
        if L[i2][1:4]==L[i][0:3]:
          dp[j][i]+=dp[j-1][i2]
    dp[j][i]%=mod
print(sum(dp[n])%mod)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    dp = [[[[0 for _ in range(4)] for _ in range(4)]
           for _ in range(4)] for _ in range(101)]
    dp[0][3][3][3] = 1
    mod = 1_000_000_007
    for n in range(100):
        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 i == 1 and a == 2) or \
                            (j == 0 and i == 2 and a == 1) or \
                            (j == 1 and i == 0 and a == 2) or \
                            (k == 0 and j == 1 and a == 2) or \
                                (k == 0 and i == 1 and a == 2):
                            continue
                        dp[n + 1][a][i][j] += dp[n][i][j][k]
                        dp[n + 1][a][i][j] %= 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)


main()

Submission status: Runtime Error

Solution code:
n = int(input())
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 = (ret + dfs(cur + 1, last3[1:]+c)) % mod
  
  memo[cur][last3] = ret
  return ret

print(dfs(0,'TTT'))

Submission status: Runtime Error

Solution code:
n = int(input())
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 = (ret + dfs(cur + 1, last3[1:]+c)) % MOD
  
  memo[cur][last3] = ret
  return ret

print(dfs(0,'TTT'))

Submission status: Runtime Error

Solution code:
n = int(input())
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 [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)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Runtime Error

Solution code:
import itertools

s = 'ACGT'
s = [a+b+c for a,b,c in itertools.product(s,s,s)]
n = {s_:1 for s_ in s}
n['AGC'] = 0
n['GAC'] = 0
n['ACG'] = 0

N = int(input())

for i in range(N-3):
    count = {s_:0 for s_ in s}
    for _ in s:
        for a in 'ACGT':
            x = _+a
            if 'GAC' in x or 'ACG' in x or ('A' == x[0] and 'GC' == x[2:]) or ('AG' == x[:2] and 'C' == x[3]):
                pass
            else:
                count[x[1:]] += n[_]
    count['AGC'] = 0
    count['GAC'] = 0
    count['ACG'] = 0
    n = count
print(sum([value for value in count.values()])%(10**9+7))

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"

for c1 in s:
  for c2 in s:
    for c3 in s:
      dp[0][c1 + c2 + c3] = 0

dp[0]["TTT"] = 1

for l in range(n):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        for p in s:
          if c2 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c3 == "G" and p == "C":
            continue
          if c1 == "A" and c2 == "G" and p == "C":
            continue
          if c2 == "G" and c3 == "A" and p == "C":
            continue
          if c2 == "A" and c3 == "C" and p == "G":
            continue
          dp[j + 1][c2 + c3 + p] += dp[j][c1 + c2 + c3]

ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

dp = {b: 1 for b in "ACGT"}
for _ in range(N - 1):
    dp_new = {}
    for k in dp:
        for b in "ACGT"
           if k[-2:] + b in ("AGC", "ACG", "GAC") or k[-3:4] + b in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                continue
            else:
                dp_new[k[-3:] + b] += dp[k]
    dp = dp_new

mod = 10 ** 9 + 7
print(sum(dp.values()) % mod)

Submission status: Runtime Error

Solution code:
N, MOD = int(input()), 10**9+7
count = 0
def dfs(index,last3):
	if index == N:
		return 1
	c_next = 'AT'
	if 'AC' in last3[1:]:
		c_next + 'G'
	if 'AG' in last3 == False:
		if  last3[1:] != 'GA':
			if last3[0]+last3[2] != 'AG':
				c_next + 'C'

	for c in c_next:
		count += dfs(index+1,last3[1:]+c)

print(dfs(0,'TTT'))

Submission status: Runtime Error

Solution code:
chars = ['A', 'G', 'C', 'T']


def is_match_agc(str):
    if str[-3:] == 'AGC':
        return True
    for i in range(3):
        strTemp = str[-4:]
        temp = strTemp[i:i+1]
        strTemp[i:i+1] = strTemp[i+1:i+2]
        strTemp[i + 1:i + 2] = temp
        if strTemp in 'AGC':
            return True
    return False


def next_str(str):
    if str[-1:] == 'T':
        return str[0:-1]
    else:
        return str + chars[chars.index(str[-1:]) + 1]


if __name__ == '__main__':
    N = int(input())
    str = 'TTT'
    counter = 0
    while str != 'TT':
        if isMatchAGC(str):
            str = next_str()
        else:
            if len(str) == N + 3:
                counter += 1
                str = next_str()
            else:
                str = str + chars[0]
    print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
memo = [{} for i in range(n+1)]
m = 10**9+7

def ppp(l):
    for i in range(4):
        t = list(l)
        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(c,l):
    if l in memo[c]:
        return memo[c][l]
    if c == n:
        return 1
    ret = 0
    for b in "AGCT":
        if ppp(l+b):
            ret = (ret + dfs(c + 1,l[1:] + c)) % m
    memo[c][l] = ret
    return ret
print(dfs(0,"TTT"))

Submission status: Runtime Error

Solution code:
n = int(input())
memo = [{} for i in range(N+1)]
m = 10**9+7

def ppp(l):
    for i in range(4):
        t = list(l)
        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(c,l):
    if l in memo[c]:
        return memo[c][l]
    if c == n:
        return 1
    ret = 0
    for b in "AGCT":
        if ppp(l+b):
            ret = (ret + dfs(c + 1,l[1:] + c)) % m
    memo[c][l] = ret
    return ret
print(dfs(0,"TTT"))

Submission status: Runtime Error

Solution code:
​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'))

Submission status: Runtime Error

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for x in range(N + 1)]
def ok(sec4):
  for i in range(4):
    tem = sec4
    if i >= 1:
      tem[i - 1], tem[i] = tem[i], tem[i - 1]  
    if tem[:3] == "AGC" or tem[1:] == "AGC":
      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 s in "AGCT":
    if ok(last3 + s):
      ret = ret + dfs(cur + 1, last3[1:] + s)
  memo[cur][last3] = ret
  return ret
print(dfs(0, "TTT") % MOD)

Submission status: Runtime Error

Solution code:
def checkAGC(string):
    str0 = string[0] +string[1] +string[2] +string[3]
    str1 = string[1] +string[0] +string[2] +string[3]
    str2 = string[0] +string[2] +string[1] +string[3]
    str3 = string[0] +string[1] +string[3] +string[2]
    
    if "AGC" in str0 or "AGC" in str1 or "AGC" in str2 or "AGC" in str3:
        return True
    else:
        return False

def checkAGC3(string):
    str0 = string[0] +string[1] +string[2]
    str1 = string[1] +string[0] +string[2] 
    str2 = string[0] +string[2] +string[1] 
    
    if "AGC" in str0 or "AGC" in str1 or "AGC" in str2 :
        return True
    else:
        return False
      

import itertools

words = list(itertools.product("ATGC", "ATGC","ATGC"))

#3文字のインデックスを返す
nucleotide_dict =  dict(list( (words[i],i) for i in range(len(words))))

import numpy as np
# 重み行列を求める
W = np.zeros((len(words),len(words)))
for word_prev in words:
    for word_next in words:
        if word_prev[1:] == word_next[:-1] and not checkAGC(word_prev[:-1]+word_next[1:]):
            #print(nucleotide_dict[word_next],nucleotide_dict[word_prev],word_prev[:-1]+word_next[1:] )
            W[nucleotide_dict[word_next],nucleotide_dict[word_prev]] = 1
b = np.array([0 if checkAGC3(i) else 1 for i in words])

def mod(num):
    return num % int(pow(10,9)+7)
  
res = b
for i in range(N-3):
    res = np.vectorize(lambda x: mod(x))(W@res)
print(int(mod(np.sum(res))))

Submission status: Runtime Error

Solution code:
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'))

Submission status: Runtime Error

Solution code:
N, MOD = int(input()), 10**9+7
memo = [{} fot 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, last[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(1,4):
        t = list(last4)
        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 "ATGC":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(1,4):
        t = list(last4)
        t[i-1], t[i] = t[i], t[i-1]
        if 'AGC' in ''.join(t):
            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 "ATGC":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(1,4):
        t = list(last4)
        t[i-1], t[i] = t[i], t[i-1]
        if 'AGC' in ''.join(t):
            return False
        else:
            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 "ATGC":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

Submission status: Runtime Error

Solution code:
N = int(input())
print((4^N - (len(N)-2)) % (10^9 + 7))

Submission status: Runtime Error

Solution code:
a=b=c=d=e=f=0;g=1;exec('a,b,c,d,e,f,g=b,e,e-d,f,g,g-c,g*4-b-c-d-a*3;'*input());print g%=10**9+7