TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
N = int(input())
ans = 0
M = (10**9)+7
dic = {}
pdic = {}
pdic['AAA'] = 1
pdic['AAC'] = 1
pdic['AAG'] = 1
pdic['AAT'] = 1
pdic['ACA'] = 1
pdic['ACC'] = 1
pdic['ACG'] = 0
pdic['ACT'] = 1
pdic['AGA'] = 1
pdic['AGC'] = 0
pdic['AGG'] = 1
pdic['AGT'] = 1
pdic['ATA'] = 1
pdic['ATC'] = 1
pdic['ATG'] = 1
pdic['ATT'] = 1
pdic['CAA'] = 1
pdic['CAC'] = 1
pdic['CAG'] = 1
pdic['CAT'] = 1
pdic['CCA'] = 1
pdic['CCC'] = 1
pdic['CCG'] = 1
pdic['CCT'] = 1
pdic['CGA'] = 1
pdic['CGC'] = 1
pdic['CGG'] = 1
pdic['CGT'] = 1
pdic['CTA'] = 1
pdic['CTC'] = 1
pdic['CTG'] = 1
pdic['CTT'] = 1
pdic['GAA'] = 1
pdic['GAC'] = 0
pdic['GAG'] = 1
pdic['GAT'] = 1
pdic['GCA'] = 1
pdic['GCC'] = 1
pdic['GCG'] = 1
pdic['GCT'] = 1
pdic['GGA'] = 1
pdic['GGC'] = 1
pdic['GGG'] = 1
pdic['GGT'] = 1
pdic['GTA'] = 1
pdic['GTC'] = 1
pdic['GTG'] = 1
pdic['GTT'] = 1
pdic['TAA'] = 1
pdic['TAC'] = 1
pdic['TAG'] = 1
pdic['TAT'] = 1
pdic['TCA'] = 1
pdic['TCC'] = 1
pdic['TCG'] = 1
pdic['TCT'] = 1
pdic['TGA'] = 1
pdic['TGC'] = 1
pdic['TGG'] = 1
pdic['TGT'] = 1
pdic['TTA'] = 1
pdic['TTC'] = 1
pdic['TTG'] = 1
pdic['TTT'] = 1
for i in range(N-3):
  for k in pdic.keys():
    k = str(k)
    if k=='ACG' or k=='AGC' or k=='GAC':
      dic[k] = 0
    elif k[1:]=='GC':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    elif k[0]=='G' and k[2]=='C':
      dic[k] = pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
    else:
      dic[k] = pdic['A'+k[:-1]]+pdic['C'+k[:-1]]+pdic['G'+k[:-1]]+pdic['T'+k[:-1]]
  for k in pdic.keys():
    pdic[k] = dic[k]
for v in dic.values():
  ans += v
  ans = ans % M
print(ans)


import numpy as np
N = int(input())
MOD = 10**9+7
dp = np.zeros(64,np.int64)
pdp = np.ones(64,np.int64)
a = 16
b = 4
pdp[0*a+2*b+1] = 0
pdp[0*a+1*b+2] = 0
pdp[2*a+0*b+1] = 0
dic = {}
dic[0] = 'A'
dic[1] = 'C'
dic[2] = 'G'
dic[3] = 'T'
for i in range(N-3):
  for j in range(64):
    x = j//16
    y = (j-x*16)//4
    z = j%4
    m = 16*y+4*z
    if y==2 and z==0:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif y==0 and z==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif y==0 and z==1:
      for h in range(4):
        if h==2:
          continue
        dp[m+h] += pdp[j]
    elif x==0 and y==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    elif x==0 and z==2:
      for h in range(4):
        if h==1:
          continue
        dp[m+h] += pdp[j]
    else:
      for h in range(4):
        dp[m+h] += pdp[j]
  dp %= MOD
  pdp = np.copy(dp)
  dp = np.zeros(64,np.int64)
print(pdp.sum()%MOD)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

N = int(input())

C = 10**9+7
n = 5
num = max(N+1, 6)
L = [0 for i in range(num)]
X = [0 for i in range(num)]
Y = [0 for i in range(num)]
Z = [0 for i in range(num)]
W = [0 for i in range(num)]
G = [0 for i in range(num)]
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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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"))

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"))

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"))

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N = int(input())
mod = 10**9+7

def check(s):
    for i in range(4):
        l=list(s)
        if i>0:
            l[i-1],l[i]=l[i],l[i-1]
        if "".join(l).count("AGC"):
            return False
    else:
        return True

memo=[dict() for _ in range(N)]
def dfp(i,seq):
    if i==N:
        return 1
    if seq in memo[i]:
        return memo[i][seq]
    ret=0
    for s in ["A","G","C","T"]:
        if check(seq+s):
            ret=(ret+dfp(i+1,seq[1:]+s))%mod
    memo[i][seq] = ret
    return ret

dfp(0,"TTT")

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

def check(s):
    for i in range(4):
        l=list(s)
        if i>0:
            l[i-1],l[i]=l[i],l[i-1]
        if "".join(l).count("AGC"):
            return False
    else:
        return True

memo=[dict() for _ in range(N)]
def dfp(i,seq):
    if i==N:
        return 1
    if seq in memo[i]:
        return memo[i][seq]
    ret=0
    for s in ["A","G","C","T"]:
        if check(seq+s):
            ret=(ret+dfp(i+1,seq[1:]+s))%mod
    memo[i][seq] = ret
    return ret

print(dfp(0,"TTT"))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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):
    print((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'))


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'))


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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'))


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'))


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache


n = int(input())

divide = 1000000007

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

out = set()
for c in agct:
    out.add('AGC' + c)
    out.add(c+'AGC')
    out.add( 'A' + c + 'GC')
    out.add('AG' + c + 'C')
    out.add('GAC' + c)
    out.add(c+'GAC')
    out.add('ACG' + c)
    out.add(c+'ACG')


def isok(str):
    if str[-4:] in out:
        return False
    return True



@lru_cache(maxsize=1000000)
def saiki(n,str):
    if n == 4:
        if isok(str):
            return 1
        return 0
    ret = 0
    if isok(str)==False:
        return 0
    for c in agct:
        next = c+str
        next = next[0:4]
        ret += saiki(n-1,next)
    return ret%divide

strlist = list(itertools.product(agct, repeat=4))

rr = 0
for strs in strlist:
    rr += saiki(n,''.join(strs))
print(rr%divide)




# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache


n = int(input())

divide = 1000000007

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

out = set()
for c in agct:
    out.add('AGC' + c)
    out.add(c+'AGC')
    out.add( 'A' + c + 'GC')
    out.add('AG' + c + 'C')
    out.add('GAC' + c)
    out.add(c+'GAC')
    out.add('ACG' + c)
    out.add(c+'ACG')


def isok(str):
    if str[-4:] in out:
        return False
    return True



@lru_cache(maxsize=1000000)
def saiki(n,str):
    if n == 4:
        if isok(str):
            return 1
        return 0
    ret = 0
    if isok(str)==False:
        return 0
    for c in agct:
        next = c+str
        next = next[0:4]
        ret += saiki(n-1,next)
    return ret%divide

strlist = list(itertools.product(agct, repeat=4))

rr = 0
for strs in strlist:
    rr += saiki(n,''.join(strs))
print(rr%divide)




# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache


n = int(input())
if n == 3:
    print('61')
    quit()

divide = 1000000007

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

out = set()
for c in agct:
    out.add('AGC' + c)
    out.add(c+'AGC')
    out.add( 'A' + c + 'GC')
    out.add('AG' + c + 'C')
    out.add('GAC' + c)
    out.add(c+'GAC')
    out.add('ACG' + c)
    out.add(c+'ACG')


def isok(str):
    if str[-4:] in out:
        return False
    return True



@lru_cache(maxsize=1000000)
def saiki(n,str):
    if n == 4:
        if isok(str):
            return 1
        return 0
    ret = 0
    if isok(str)==False:
        return 0
    for c in agct:
        next = c+str
        next = next[0:4]
        ret += saiki(n-1,next)
    return ret%divide

strlist = list(itertools.product(agct, repeat=4))

rr = 0
for strs in strlist:
    rr += saiki(n,''.join(strs))
print(rr%divide)




Verdicts: Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
# AGCT -> 0123






# S + 0


# S + 3






import numpy as np

N = int(input())

mod = 10 ** 9 + 7

memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1


for c in range(N):
    
    for i in range(4):
        
        for j in range(4):
            
            for k in range(4):
                
                for a in range(4):
                    
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

print(memo)

ans = 0

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


# AGCT -> 0123






# S + 0


# S + 3






import numpy as np

N = int(input())

mod = 10 ** 9 + 7

memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1


for c in range(N):
    
    for i in range(4):
        
        for j in range(4):
            
            for k in range(4):
                
                for a in range(4):
                    
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod


ans = 0

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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N = int(input())

mod = 10 ** 9 + 7

result = 3
for i in range(3, N):
    result = (4 * result + 2) % mod
print(result)



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

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

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

def dfs(cur, S):
    if S in memo[cur]:
        return memo[cur][S]
    if cur == N:
        return 1

    count = 0
    for c in "ACGT":
        if valid(S + c):
            count = (count + dfs(cur + 1, S[1:] + c)) % mod
    memo[cur][S] = count
    return count

print(dfs(0, "TTT"))


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
# D
mod = 10**9+7
n = int(input())
ans = (4**n - (3*4**(n-3)*(n-2) + 2*4**(n-4)*(n-3))) % mod
print(ans)

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], t[i - 1] = t[i - 1], t[i]
        if ''.join(t).find('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 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
typedef long long ll;

const int maxn = 110;

int N;

vector<unordered_map<string, ll>> memo(maxn);

bool check(string last4) {
    if (last4.find("AGC") != string::npos) {
        return false;
    }
    for (int i = 0; i < 4 - 1; ++i) {
        swap(last4[i], last4[i + 1]);
        if (last4.find("AGC") != string::npos) {
            return false;
        }
        swap(last4[i], last4[i + 1]);
    }
    return true;
}

ll dfs(int cur, const string& last3) {
    if (memo[cur].count(last3)) {
        return memo[cur][last3];
    }
    if (cur == N) {
        return 1;
    }
    ll ret = 0;
    for (char c : string("ACGT")) {
        if (check(last3 + c)) {
            ret = (ret % MOD + dfs(cur + 1, last3.substr(1) + c) % MOD) % MOD;
        }
    }
    return memo[cur][last3] = ret;
}

int main() {
    cin >> N;
    cout << dfs(0, "TTT") << endl;
    return 0;
}

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 'AGCT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N = int(input())

MOD = 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
A = 1
C = 2
G = 3
T = 4

for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(1, 5):
                    if p == A and q == G and s == C: 
                        continue
                    if p == A and r == G and s == C:
                        continue
                    if q == A and r == G and s == C: 
                        continue
                    if q == G and r == A and s == C:
                        continue
                    if q == A and r == C and s == G: 
                        continue
                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD

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

print(dp) 

N = int(input())

MOD = 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
A = 1
C = 2
G = 3
T = 4

for i in range(N):
    for p in range(5):
        for q in range(5):
            for r in range(5):
                for s in range(1, 5):
                    if p == A and q == G and s == C: 
                        continue
                    if p == A and r == G and s == C:
                        continue
                    if q == A and r == G and s == C: 
                        continue
                    if q == G and r == A and s == C:
                        continue
                    if q == A and r == C and s == G: 
                        continue
                    dp[i+1][q][r][s] += dp[i][p][q][r]
                    dp[i+1][q][r][s] %= MOD

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

print(ans) 

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N, MOD = int(input()), 10**9 
memo = [{} for x 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'))


N, MOD = int(input()), 10**9 
memo = [{} for x 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'))

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)

N, MOD = int(input()), 10**9 + 7
memo = [{} for x 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'))


N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for x in range(N + 1)]
def ok(sec4):
  for i in range(4):
    tem = list(sec4)
    if i >= 1:
      tem[i - 1], tem[i] = tem[i], tem[i - 1]
    tem2 = "".join(tem)  
    if tem2[:3] == "AGC" or tem2[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)

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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))

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())
if N == 3:
    count = n
else:
    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))

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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;'*int(input()));print(g%(1e9+7))

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))%(10**9+7);'*int(input()));print(g)

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)%(10**9+7);'*int(input()));print(g)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
def dfs(index, last, string, memo):
    mod = 10 ** 9 + 7
    if string in memo[index]:
        return memo[index][string]
    if index == last:
        return 1

    ret = 0
    for s in "ACGT":
        if check(string + s):
            ret = (ret + dfs(index + 1, last, string[1:] + s, memo)) % mod
    memo[index][string] = ret
    return ret


def check(string):
    for i in range(4):
        s_list = list(string)
        if i >= 1:
            s_list[i-1], s_list[i] = s_list[i], s_list[i-1]
        if "".join(s_list).count("AGC") >= 1:
            return False
    return True


def main():
    n = int(input())
    memo = [{} for _ in range(n+1)]

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


if __name__ == "__main__":
    main()

def dfs(index, last, string, memo):
    mod = 10 ** 9 + 7
    if string in memo[index]:
        return memo[index][string]
    if index == last:
        return 1

    ret = 0
    for s in "ACGT":
        if check(string + s):
            ret = (ret + dfs(index + 1, last, string[1:] + s, memo)) % mod
    memo[index][string] = ret
    return ret


def check(string):
    for i in range(4):
        s_list = list(string)
        if i >= 1:
            s_list[i-1], s_list[i] = s_list[i], s_list[i-1]
        if "".join(s_list).count("AGC") >= 1:
            return False
    return True


def main():
    n = int(input())
    memo = [{} for _ in range(n+1)]

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


if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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 'AGCT':
        if ok(last3+c):
            ret = (ret + dfs(cur+1,last3[1:]+c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

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 'AGCT':
        if ok(last3+c):
            ret = (ret + dfs(cur+1,last3[1:]+c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0,'TTT'))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
#A,G,C,T=0,1,2,3


n=int(input())
A=[[1,1,1,1],[1,1,0,1],[1,0,1,1],[1,1,1,1]] 
B=[[3,3,2,3],[3,3,3,3],[3,3,3,3],[3,3,3,3]] 
mod=10**9+7

for _ in range(n-3):
    nA=[[0]*4 for i in range(4)]
    nB=[[0]*4 for i in range(4)]
    for i in range(4):
        for j in range(4): 
            if j!=3: 
                if not (i==2 and j==1): #ACG
                    nA[i][j]+=A[0][i]
                nB[i][j]+=A[1][i]
                nB[i][j]+=A[2][i]
                nB[i][j]+=A[3][i]
            else: 
                if i!=1: #A?GC
                    nA[i][j]+=A[0][i]
                    #nB[i][j]+=A[1][i] #AG?C
                    nB[i][j]+=A[2][i]
                    nB[i][j]+=A[3][i]
            
            if not i*j==2: #AGC,ACG
                nA[i][j]+=B[0][i]
            if not (i==0 and j==2): #GAC
                nB[i][j]+=B[1][i]
            nB[i][j]+=B[2][i]
            nB[i][j]+=B[3][i]
    for a in nA:
        for i in range(4):
            a[i]%=mod
    for b in nB:
        for i in range(4):
            b[i]%=mod
    A=nA
    B=nB
    
ans=0
for a in A:
    ans+=sum(a)%mod
for b in B:
    ans+=sum(b)%mod
print(A,B)
print(ans%mod)

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


import copy

n=int(input())
A=[[1,1,1,1],[1,1,0,1],[1,0,1,1],[1,1,1,1]] 
B=[[3,3,2,3],[3,3,3,3],[3,3,3,3],[3,3,3,3]] 
mod=10**9+7

for _ in range(n-3):
    nA=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    nB=[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
    for i in range(4):
        for j in range(4): 
            if j!=2: 
                if not (i==2 and j==1): #ACG
                    nA[i][j]+=A[0][i]
                nB[i][j]+=A[1][i]
                nB[i][j]+=A[2][i]
                nB[i][j]+=A[3][i]
            else: 
                if i!=1: #A?GC
                    nA[i][j]+=A[0][i]
                    #nB[i][j]+=A[1][i] #AG?C
                    nB[i][j]+=A[2][i]
                    nB[i][j]+=A[3][i]
            
            if not i*j==2: #AGC,ACG
                nA[i][j]+=B[0][i]
            if not (i==0 and j==2): #GAC
                nB[i][j]+=B[1][i]
            nB[i][j]+=B[2][i]
            nB[i][j]+=B[3][i]
    for a in nA:
        for i in range(4):
            a[i]%=mod
    for b in nB:
        for i in range(4):
            b[i]%=mod
    A=copy.copy(nA)
    B=copy.copy(nB)
    
ans=0
for a in A:
    ans+=sum(a)%mod
for b in B:
    ans+=sum(b)%mod 
print(ans%mod)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N = int(input())

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

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

    num = num_now.copy()


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


N = int(input())

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

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

    num = num_now.copy()


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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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:] + b)) % m
    memo[c][l] = ret
    return ret
print(dfs(0,"TTT"))

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"))

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"))

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:] + b)) % m
    memo[c][l] = ret
    return ret
print(dfs(0,"TTT"))

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
mod = 10**9+7

a = [1,4]
c = [1,4]
g = [1,4]
t = [1,4]

for i in range(2,n):
  p = (a[i-1]+g[i-1]+c[i-1]+t[i-1])
  a.append(p)
  g.append(p-a[i-2])
  if i > 2:
    c.append(p-a[i-2]-g[i-2]-a[i-3]*2)
  else:
    c.append(p-a[i-2]-g[i-2])
  t.append(p)
print(a[-1]+t[-1]+g[-1]+c[-1])
print((a[-1]+t[-1]+g[-1]+c[-1])%mod)

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from functools import lru_cache

n = ni()
mod = 10**9+7

@lru_cache(maxsize=10000)
def dfs(n, l):
    rt = 0
    if n == 0:
        return 1
    if l[1:3] == 'AG' or l[1:3] == 'GA' or (l[0] == 'A' and l[2] == 'G') or l[:2] == 'AG':
        pass
    else:
        rt += dfs(n-1, l[1:]+'C')
    if l[1:] != 'AC':
        rt += dfs(n-1,l[1:]+'G')
    rt += dfs(n-1,l[1:]+'T')
    rt += dfs(n-1,l[1:]+'A')
    return rt%mod

print(dfs(n,'TTT')%mod)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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 "AGCT":
        if ok(last3+c):
            ret = (ret + dfs(cur+1,last3[1:]+c)) % mod
    memo[cur][last3] = ret
    return ret

print(memo)

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 "AGCT":
        if ok(last3+c):
            ret = (ret + dfs(cur+1,last3[1:]+c)) % mod
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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"))


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:]):
            
            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))))

N = int(input())

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"))


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:]):
            
            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))(np.dot(W,res))
print(int(mod(np.sum(res))))


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
a,g,a_,a__,ac,ga,al=[0]*6+[1]
for i in range(int(input())):
    a__,a_,ac,ga,a,g,al=a_,a,a-ga,g,al,al-ac,(al*4-(ag+ac+ga+a__*3))%(pow(10,9)+7)
print(al)


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;'*int(input()));print(g%(10**9+7))

Verdicts: Runtime Error

Accepted