TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
n, q = map(int, input().split())
s = input()
lis=[]
for i in range(q):
    lis.append(list(map(int, input().split())))
idx=0
acs=[0]*n
for _ in s:
    if s[idx]=="A" and s[idx+1]=="C":
        acs[idx+1] = 1
        idx+=1
    idx+=1
    if idx>=(len(s)-1):
        break
cnt=0
print(acs)
for i,el in enumerate(acs):
    if el!=0:
        cnt+=el
        acs[i]=cnt
    else:
        acs[i]=cnt
print(acs)
for i in lis:
    print(acs[i[1]-1]-acs[i[0]-1])

n, q = map(int, input().split())
s = input()
lis=[]
for i in range(q):
    lis.append(list(map(int, input().split())))
idx=0
acs=[0]*n
for _ in s:
    if s[idx]=="A" and s[idx+1]=="C":
        acs[idx+1] = 1
        idx+=1
    idx+=1
    if idx>=(len(s)-1):
        break
cnt=0
#print(acs)
for i,el in enumerate(acs):
    if el!=0:
        cnt+=el
        acs[i]=cnt
    else:
        acs[i]=cnt
#print(acs)
for i in lis:
    print(acs[i[1]-1]-acs[i[0]-1])


Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
import bisect
N, Q = map(int, input().split())
S = input()
arr = []
for i in range(N-1):
  if S[i:i+2] == "AC":
    arr.append(i)
print(arr)
for i in range(Q):
  l, r = map(int, input().split())
  print(bisect.bisect_right(arr, r-2) - bisect.bisect_left(arr, l-1))
               

import bisect
N, Q = map(int, input().split())
S = input()
arr = []
for i in range(N-1):
  if S[i:i+2] == "AC":
    arr.append(i)
#print(arr)
for i in range(Q):
  l, r = map(int, input().split())
  print(bisect.bisect_right(arr, r-2) - bisect.bisect_left(arr, l-1))
               

Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
n,q = map(int,input().split())
s = input()

li = [0]*n

for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        li[i] += 1

from itertools import accumulate

lin = [0]+list(accumulate(li))
print(lin)
for _ in range(q):
    l,r = map(int,input().split())
    print(lin[r]-lin[l])

n,q = map(int,input().split())
s = input()

li = [0]*n

for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        li[i] += 1

from itertools import accumulate

lin = [0]+list(accumulate(li))

for _ in range(q):
    l,r = map(int,input().split())
    print(lin[r]-lin[l])

Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = (1 if s[i:i + 2] == "AC" else 0) + t[i]
print(t)
for i in range(q):
    l, r = list(map(int, input().split()))
    print(t[r - 1] - t[l - 1])


n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = (1 if s[i:i + 2] == "AC" else 0) + t[i]
for i in range(q):
    l, r = list(map(int, input().split()))
    print(t[r - 1] - t[l - 1])


Verdicts: Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
N , Q = map(int,input().split())
S = input()
L = [list(map(int,input().split())) for i in range(Q)]

cut = ""

conlist = []

for i in range(Q):
	cut = S[L[i][0]-1:L[i][1]+1]
	conlist.append(cut.count("AC"))
	
print(max(conlist))

N , Q = map(int,input().split())
S = input()
L = [list(map(int,input().split())) for i in range(Q)]

cut = ""

con = 0

for i in range(Q):
	cut = S[L[i][0]-1:L[i][1]]
	num = cut.count("AC")
	if num > con:
		con = num

print(con)

N,Q = map(int,input().split())
S = input()
L = [list(map(int,input().split())) for i in range(Q)]

for c in range(Q):
  l = L[c][0] - 1
  r = L[c][1] - 1
  part = S[l:r]
  print(part.count("AC"))
  
  

N , Q = map(int,input().split())
S = input()
L = [list(map(int,input().split())) for i in range(Q)]

cut = ""

conlist = []

for i in range(Q):
	cut = S[L[i][0]-1:L[i][1]]
	conlist.append(cut.count("AC"))
	print(cut)
print(max(conlist))

N , Q = map(int,input().split())
S = input()
L = [list(map(int,input().split())) for i in range(Q)]

cut = ""

con = 0

for i in range(Q):
	cut = S[L[i][0]-1:L[i][1]]
	num = cut.count("AC")
	if num > con:
		con = num

print(con)

N, Q = map(int, input().split())
S = input()
cons = [0] * (N + 1)

for i in range(N - 1):
  
  
  
  cons[i + 1] = cons[i] + (1 if S[i] + S[i + 1] == 'AC' else 0)

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

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
n,q = map(int,input().split())
s = input()
ans = []
for i in range(q):
    l,r = map(int,input().split())
    buf = s[l-1:r]
    print(buf)
    ans.append(buf.count('AC'))

for i in range(len(ans)):
    print(ans[i])


n,q = map(int,input().split())
s = input()
ans = []
li = [0] * (len(s))
count = 0

for i in range(1,len(s)):
    if s[i] == 'C' and s[i-1] == 'A':
        count += 1
    li[i] = count

for i in range(q):
    l,r = map(int,input().split())
    tmp = li[r-1] - li[l-1]
    ans.append(tmp)

for aa in ans:
    print(aa)


Verdicts: Runtime Error

Accepted
Problem: You are given a string S of length N consisting of `A`, `C`, `G` and `T`. Answer the following Q queries:    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?

Submission attempts (in order):
N, Q = map(int, input().split())
S = input()
flag = True
R = [0]*N
a = 0
for i in range(N):
    s = S[i]
    if s == "A":
        flag = True
    elif s == "C" and flag:
        a += 1
        flag = False
    else:
        flag = False
    R[i] = a
print(R)
for i in range(Q):
    l, r = map(int, input().split())
    print(R[r-1] - R[l-1])


N, Q = map(int, input().split())
S = input()
flag = True
R = [0]*N
a = 0
for i in range(N):
    s = S[i]
    if s == "A":
        flag = True
    elif s == "C" and flag:
        a += 1
        flag = False
    else:
        flag = False
    R[i] = a
for i in range(Q):
    l, r = map(int, input().split())
    print(R[r-1] - R[l-1])


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):
dp=[0]*101
dp[3]=61
p=10**9+7
for i in range(4,101):
  dp[i]=(dp[i-1]*4-pow(4,i-3,p)*3-pow(4,i-4,p))%p
print(dp[100])

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

dp=[0]*101
dp[3]=61
dp[4]=230
dp[5]=864
dp[6]=3232
p=10**9 +7
for i in range(4,101):
  dp[i]=(4*dp[i-1]-14*dp[i-4])%p
print(dp[100])

dp=[[[[0]*4 for i in range(4)] for i in range(4)] for i in range(101)]
dp[0][3][3][3]=1
mod=10**9+7

for length in range(100):
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        if dp[length][c1][c2][c3]==0:
          continue
        for a in range(4):
          if c2==0 and c3==1 and a==2:
            continue
          if c2==1 and c3==0 and a==2:
            continue
          if c2==0 and c3==2 and a==1:
            continue
          if c1==0 and c3==1 and a==2:
            continue
          if c1==0 and c2==1 and a==2:
            continue
          dp[length+1][c2][c3][a]+=dp[length][c1][c2][c3]
          dp[length+1][c2][c3][a]%mod

n=int(input())
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)

Verdicts: Wrong Answer

Wrong Answer

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

print(m)

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



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


using namespace std;
const long long INF = 1000000007ll;
int k[4];
void ku(int a) {
  for (int i = 3; i >= 0; i --) {
    k[i] = a % 4;
    a /= 4;
  }
}
bool ok(int a) {
  for (int i = 0; i < 4; i ++) {
    ku(a);
    if (i >= 1) swap(k[i - 1], k[i]);
    if (k[0] == 0 && k[1] == 1 && k[2] == 2) return false;
    if (k[1] == 0 && k[2] == 1 && k[3] == 2) return false;
  }
  return true;
}
int N;
vector<vector<long long>>memo(101, vector<long long>(64, -1));
long long dfs(int cur, int last3) {
  if (memo[cur][last3] != -1) return memo[cur][last3];
  if (cur == N) return 1;
  long long ret = 0;
  for (int i = 0; i < 4; i ++) {
    if (ok(last3 * 4 + i)) {
      int jun = last3 % 16;
      jun *= 4;
      jun += i;
      ret = (ret + dfs(cur + 1, jun)) % INF;
    }
  }
  memo[cur][last3] = ret;
  return ret;
}
int main () {
  cin >> N;
  cout << dfs(0, 63) << endl;
}
  




using namespace std;
const long long INF = 1000000007ll;
int k[4];
void ku(int a) {
  for (int i = 3; i >= 0; i --) {
    k[i] = a % 4;
    a /= 4;
  }
}
bool ok(int a) {
  for (int i = 0; i < 4; i ++) {
    ku(a)
    if (i >= 1) swap(k[i - 1], k[i]);
    if (k[0] == 0 && k[1] == 1 && k[2] == 2) return false;
    if (k[1] == 0 && k[2] == 1 && k[3] == 2) return false;
  }
  return true;
}
int N;
vector<vector<long long>>memo(101, vector<long long>(64, -1));
long long dfs(int cur, int last3) {
  if (memo[cur][last3] != -1) return memo[cur][last3];
  if (cur == N) return 1;
  long long ret = 0;
  for (int i = 0; i < 4; i ++) {
    if (ok(last3 * 4 + i)) {
      int jun = last3 % 16;
      jun *= 4;
      jun += i;
      ret = (ret + dfs(cur + 1, jun)) % INF;
    }
  }
  memo[cur][last3] = ret;
  return ret;
}
int main () {
  cin >> N;
  cout << dfs(0, 63) << endl;
}
  


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

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 -*-
"""
Created on Sun Mar 24 20:51:04 2019

@author: Yamazaki Kenichi
"""

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

res = [[0 for j in range(14)] for i in range(N+1)]
res[1][0],res[1][1],res[1][2],res[1][3] = 1,1,1,1


for i in range(2,N+1):
    res[i][0] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][2]-res[i-1][4]-res[i-1][11]-res[i-1][12]-res[i-1][13]
    res[i][1] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][10]-res[i-1][11]-res[i-1][12]-res[i-1][13]
    res[i][2] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]-res[i-1][6]-res[i-1][7]-res[i-1][12]-res[i-1][5]
    res[i][3] = sum(res[i-1]) - (res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    )-res[i-1][4]
    res[i][4] = res[i-1][0]            +res[i-1][8]+res[i-1][9]
    res[i][5] = res[i-1][0]+res[i-1][6]
    res[i][6] = res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    res[i][7] = res[i-1][0]+res[i-1][6]+res[i-1][8]+res[i-1][9]
    res[i][8] = res[i-1][2]+res[i-1][11]+res[i-1][13]
    res[i][9] = res[i-1][4]+res[i-1][12]
    res[i][10] = res[i-1][4]+res[i-1][12]
    res[i][11] = res[i-1][4]+res[i-1][12]
    res[i][12] = res[i-1][6]
    res[i][13] = res[i-1][7]

print(sum(res[-1])%mod)

# -*- coding: utf-8 -*-
"""
Created on Mon Apr  1 18:53:11 2019

@author: Yamazaki Kenichi
"""

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]
#        print(t)
        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':
#        print(last3 + c)
#        print(ok(last3 + c))
        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):
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)

n = int(input())
dp = [{} for i in range(n + 1)]
s = "AGCT"
M = 10 ** 9 + 7
 
for j in range(n + 1):
  for c1 in s:
    for c2 in s:
      for c3 in s:
        dp[j][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[l + 1][c2 + c3 + p] += dp[l][c1 + c2 + c3]
          dp[l + 1][c2 + c3 + p] = dp[l + 1][c2 + c3 + p] % M
 
ans = 0
for c1 in s:
  for c2 in s:
    for c3 in s:
      ans += dp[n][c1 + c2 + c3]
      ans = ans % M
print(ans)

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
ans = 0
k = []
d = []
def calc(l, ans):
    if len(l) == n:
        for al in ["AGC", "GAC", "ACG", "AGGC", "ATGC", "ACGC", "AGTC", "AGAC", "AGGC"]:
            if al in l:
                return ans
        return ans + 1
    for alphabet in "AGCT":
        ll = l + alphabet
        ans = calc(ll, ans)
    return ans
calc("", ans) % mod

import copy

def ok(len_4):    
    for i in range(3):
        alpha = list(copy.deepcopy(len_4))
        alpha[i], alpha[i + 1] = alpha[i + 1], alpha[i]
        if "AGC" in "".join(alpha):
            return False
    if "AGC"in len_4:
        return False
    return True


def check(len_3, n):
    if n == N:
        return 1
    if len_3 in memo[n]:
        return memo[n][len_3]
    ret = 0
    for alpha in "AGCT":
        t = len_3 + alpha
        if ok(t):
            temp = check(t[1:], n + 1)
            memo[n + 1][t[1:]] = temp % mod
            ret += temp % mod
    return ret % mod


mod = (10 ** 9) + 7
N = int(input())
memo = [{} for _ in range(N + 1)]
check("TTT", 0)

import copy

def ok(len_4):    
    for i in range(3):
        alpha = list(copy.deepcopy(len_4))
        alpha[i], alpha[i + 1] = alpha[i + 1], alpha[i]
        if "AGC" in "".join(alpha):
            return False
    if "AGC"in len_4:
        return False
    return True


def check(len_3, n):
    if n == N:
        return 1
    if len_3 in memo[n]:
        return memo[n][len_3]
    ret = 0
    for alpha in "AGCT":
        t = len_3 + alpha
        if ok(t):
            temp = check(t[1:], n + 1)
            memo[n + 1][t[1:]] = temp % mod
            ret += temp % mod
    return ret % mod


mod = (10 ** 9) + 7
N = int(input())
memo = [{} for _ in range(N + 1)]
ans = check("TTT", 0)
print(ans)

Verdicts: Wrong Answer

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):
ngs4 = ["ATGC", "AGTC","ACGC", "AGCC","AGGC", "AGGC"]
ngs3 = ["AGC", "ACG", "GAC"]
def is_valid(b):
    s = b[-4:]
    if s in ngs4:
        return False
    s = s[-3:]
    if s in ngs3:
        return False
    return True

N = int(input())
memo = [{} for i in range(N+1)]
acgt = ["A", "C", "G", "T"]
MOD = 10**9 + 7
def dp(i, last3):
    if last3 in memo[i]:
        return memo[i][last3]

    if i == N:
        return 1
    
    ret = 0
    for c in acgt:
        candi = last3 + c
        if is_valid(candi):
            ret = (ret + dp(i+1, last3[1:] +c)) % MOD
    memo[i][last3] = ret
    return ret

def sub():
    print(dp(0, "TTT"))


ngs4 = ["ATGC", "AGTC","ACGC", "AGCC","AGGC", "AGGC"]
ngs3 = ["AGC", "ACG", "GAC"]
def is_valid(b):
    s = b[-4:]
    if s in ngs4:
        return False
    s = s[-3:]
    if s in ngs3:
        return False
    return True

N = int(input())
memo = [{} for i in range(N+1)]
acgt = ["A", "C", "G", "T"]
MOD = 10**9 + 7
def dp(i, last3):
    if last3 in memo[i]:
        return memo[i][last3]

    if i == N:
        return 1
    
    ret = 0
    for c in acgt:
        candi = last3 + c
        if is_valid(candi):
            ret = (ret + dp(i+1, last3[1:] +c)) % MOD
    memo[i][last3] = ret
    return ret

def sub():
    print(dp(0, "TTT"))

sub()


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

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







def dfs(index,last3):
	if last3 in memo[index]:
		return memo[index][last3]
	if index == N:
		return 1
	c_next = 'AT'
	if last3[1:] != 'AC':
		c_next += 'G'
	if ('AG' in last3) == False:
		if  last3[1:] != 'GA':
			if last3[0]+last3[2] != 'AG':
				c_next += 'C'
	count = 0
	for c in c_next:
		count += dfs(index+1,last3[1:]+c)
		count %= MOD

	memo[index][last3] = count
	return count

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())
if n==3:
    print(61)
if n==4:
    print(230)
l=['A','C','G','T']
dic3=dict('AGC'=1,'ACG'=1,'GAC'=1)
dic4=dict('AGTC'=1,'AGGC'=1,'ATGC'=1)
ans=0
z=[]
for a in range(4):
    for b in range(4):
        for c in range(4):            
            for d in range(4):
                f=0
                s=""
                s+=l[a]
                s+=l[b]
                s+=l[c]
                s+=l[d]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f==0:
                    ans+=1
                    z+=[s]
n=n-4

if n>0:
    for i in range(n):
        ans*=4
        for j in range(len(z)):
            for k in range(4):
                f=0
                s=z[1:4]+l[k]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f>0:
                    ans-=1
    print(ans)
                

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=[]
for j in zt:
    if not j in ng:
        z.append(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)


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):
#!/usr/bin/env python3
import copy

n = int(input())

mod = 10**9+7

miss = set(["AGC", "ACG", "GAC"])
# miss = set([])


ans = {"AA": 1, "AC": 1, "AG": 1, "AT": 1,
       "CA": 1, "CC": 1, "CG": 1, "CT": 1,
       "GA": 1, "GC": 1, "GG": 1, "GT": 1,
       "TA": 1, "TC": 1, "TG": 1, "TT": 1}

ans_base = {"AA": 0, "AC": 0, "AG": 0, "AT": 0,
            "CA": 0, "CC": 0, "CG": 0, "CT": 0,
            "GA": 0, "GC": 0, "GG": 0, "GT": 0,
            "TA": 0, "TC": 0, "TG": 0, "TT": 0}

AG = [0, 1]
for i in range(2, n):
    ans_pre = copy.deepcopy(ans)
    ans = copy.deepcopy(ans_base)
    print(ans_pre)
    for key in ans_pre.keys():

        for l in ["A", "C", "G", "T"]:

            if key+l in miss:
                print(key+l)
                continue
            else:
                # print((key+l))
                ans[(key+l)[1:]] += ans_pre[key] % mod
    AG.append(ans["AG"])
    print(AG)
    ans["AC"] -= AG[-3]
    ans["GC"] -= AG[-3]
    ans["TC"] -= AG[-3]


print(sum(ans.values()) % mod)


# AA
# AC
# AG
# AT
# CA
# CC
# CG
# CT
# GA
# GC
# GG
# GT
# TA
# TC
# TG
# TT


#!/usr/bin/env python3
import copy

n = int(input())

mod = 10**9+7

memo = {}

banned = {'ACTG', 'TCAG', 'GCAG', 'TACG', 'AACG', 'ACAG', 'GAGC', 'CACG',
          'AGC', 'ATCG', 'ACCG', 'CAG', 'GACG', 'CCAG', 'AAGC', 'ACG', 'TAGC'}

count = 0


def dp(lettrs, state):

    if state in banned:
        return 0
    if lettrs == 0:
        return 1
    if (lettrs, state) in memo:
        return memo[lettrs, state]

    ans = 0
    for c in "ACGT":
        ans += dp(lettrs-1, (state+c)[-4:])
        ans %= mod
    ans %= mod
    memo[lettrs, state] = ans

    return ans


print(dp(n, ""))
# print(memo)
# AG = [0, 1]

#     ans_pre = copy.deepcopy(ans)
#     ans = copy.deepcopy(ans_base)
#     print(ans_pre)
#     for key in ans_pre.keys():

#         for l in ["A", "C", "G", "T"]:

#             if key+l in miss:
#                 print(key+l)
#                 continue
#             else:
#                 # print((key+l))

#     AG.append(ans["AG"])
#     print(AG)
#     ans["AC"] -= AG[-3]
#     ans["GC"] -= AG[-3]
#     ans["TC"] -= AG[-3]


# print(sum(ans.values()) % mod)

# AA
# AC
# AG
# AT
# CA
# CC
# CG
# CT
# GA
# GC
# GG
# GT
# TA
# TC
# TG
# TT


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
dp = [ [ [ [0] * 4 ] * 4 ] * 4 ] * 101

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

for length in range(N):
  for i in range(4):
    for j in range(4):
      for k in range(4):
        if dp[length][i][j][k] == 0: continue
        for a in range(a):
          if a == 2 and i == 1 and j == 0: continue
          if a == 2 and i == 0 and j == 1: continue
          if a == 1 and i == 2 and j == 0: continue
          if a == 2 and i == 1 and k == 0: continue
          if a == 2 and j == 1 and k == 0: continue
          dp[length + 1][a][i][j] += dp[length][i][j][k]
          dp[length + 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)


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)


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 = [{} 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'))

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


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

memo = [{'AGC':0, 'ACG':0, 'GAC':0} for i in range(N + 4)]
C = list('ACGT')
for c in itertools.product(C, C, C):
    c = ''.join(c)
    if c in memo[3]:
        continue
    else:
        memo[3][c] = 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]
    ret = 0
    for c in 'ACGT':
        if ok(c + last3):
            ret = (ret + dfs(cur - 1, c + last3[:-1])) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(N + 3, '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):
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7)

import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.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):
iimport re
import functools

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


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


print(dfs(0, 'TTT'))

import re
import functools

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


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


print(dfs(0, 'TTT'))

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 -*-

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)


# -*- 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":
            n = k[-3:] + b
            if n[-3:] in ("AGC", "ACG", "GAC") or n in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                continue
            else:
                if n in dp_new:
                    dp_new[n] += dp[k]
                else:
                    dp_new[n] = dp[k]
    dp = dp_new

print(sum(dp.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):
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, 'AAA'))


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):
n = int(input())
mod = 10**9+7
A=[1] + [0]*(n-1)
G=[1] + [0]*(n-1)
C=[1] + [0]*(n-1)
for i in range(1,n):
    t=(2*A[i-1]+G[i-1]+C[i-1])%mod
    A[i]=t
    G[i]=(t-A[i-2]+G[i-3])%mod
    C[i]=(t-A[i-2]-G[i-2]-3*A[i-3])%mod
print((2*A[-1]+G[-1]+C[-1])%mod)


n = int(input())
mod = 10**9+7
A=[1] + [0]*(n+3)
G=[1] + [0]*(n+3)
C=[1] + [0]*(n+3)
for i in range(1,n):
    t=(2*A[i-1]+G[i-1]+C[i-1])%mod
    A[i]=t
    G[i]=(t-A[i-2]+G[i-3])%mod
    C[i]=(t-A[i-2]-G[i-2]-3*A[i-3])%mod
print((2*A[n-1]+G[n-1]+C[n-1])%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())
a=3
count=4**N-3*8**N-2*(N-3)
print(count)

import numpy as np
N=int(input())
#AGCT
#0123
dp = np.zeros((N+1, 4, 4, 4))
dp[0][3][3][3]=1
mod=1000000007
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):
          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
          dp[c+1][a][i][j]+=dp[c][i][j][k]
          dp[c+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(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, 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"))
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 "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):
N = int(input())

mod = 10 ** 9 + 7

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

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

print(dp)
for i in range(N):
    for j in range(4):
        for k in range(4):
            for m in range(4):
                if dp[i][j][k][m] == 0:
                    continue
                for l in range(4):
                    if l == 2 and j == 1 and k == 0:
                        continue
                    if l == 2 and j == 0 and k == 1:
                        continue
                    if l == 1 and j == 2 and k == 0:
                        continue
                    if l == 2 and j == 1 and m == 0:
                        continue
                    if l == 2 and k == 1 and m == 0:
                        continue
                    dp[i + 1][l][j][k] += dp[i][j][k][m]
                    dp[i + 1][l][j][k] %= mod

ans = 0
print(dp)
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)


N = int(input())

mod = 10 ** 9 + 7

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

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

for i in range(N):
    for j in range(4):
        for k in range(4):
            for m in range(4):
                if dp[i][j][k][m] == 0:
                    continue
                for l in range(4):
                    if l == 2 and j == 1 and k == 0:
                        continue
                    if l == 2 and j == 0 and k == 1:
                        continue
                    if l == 1 and j == 2 and k == 0:
                        continue
                    if l == 2 and j == 1 and m == 0:
                        continue
                    if l == 2 and k == 1 and m == 0:
                        continue
                    dp[i + 1][l][j][k] += dp[i][j][k][m]
                    dp[i + 1][l][j][k] %= 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)


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):
import itertools as it

N=int(input())
dp=dict()
def ok(s):
    return all(['AGC' not in t for t in 
        [s, s[0:2]+s[3]+s[2], s[0]+s[2]+s[1]+s[3], s[1]+s[0]+s[2:4]]]) 

def n(j, s):
    print(j, s)
    if j == 3:
        return 1 if s not in ["AGC", "ACG", "GAC"] else 0
    if (j, s) in dp:
        return dp[(j, s)]
    ret = sum([
        n(j-1, "A"+s[:3]) if ok("A"+s[:3]) else 0,
        n(j-1, "C"+s[:3]) if ok("C"+s[:3]) else 0,
        n(j-1, "G"+s[:3]) if ok("G"+s[:3]) else 0,
        n(j-1, "T"+s[:3]) if ok("T"+s[:3]) else 0]
    )
    dp[(j, s)]=ret
    return ret

m=sum([n(N, "".join(s)) for s in it.product("ACGT", repeat=3)])
print(m%(10**9+7))

import itertools as it

N=int(input())
dp=dict()
def ok(s):
    return all(['AGC' not in t for t in 
        [s, s[0:2]+s[3]+s[2], s[0]+s[2]+s[1]+s[3], s[1]+s[0]+s[2:4]]]) 

def n(j, s):
    if j == 3:
        return 1 if s not in ["AGC", "ACG", "GAC"] else 0
    if (j, s) in dp:
        return dp[(j, s)]
    ret = sum([
        n(j-1, "A"+s[:3]) if ok("A"+s[:3]) else 0,
        n(j-1, "C"+s[:3]) if ok("C"+s[:3]) else 0,
        n(j-1, "G"+s[:3]) if ok("G"+s[:3]) else 0,
        n(j-1, "T"+s[:3]) if ok("T"+s[:3]) else 0]
    )
    dp[(j, s)]=ret
    return ret

m=sum([n(N, "".join(s)) for s in it.product("ACGT", repeat=3)])
print(m%(10**9+7))

Verdicts: Wrong Answer

Accepted