Problem:


Score : 400 points

Problem Statement

You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

The string does not contain characters other than A, C, G and T.

The string does not contain AGC as a substring.

The condition above cannot be violated by swapping two adjacent characters once.

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and  (the empty string), but not AC.

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Sample Input 1

3

Sample Output 1

61

There are 4^3 = 64 strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64 - 3 = 61.

Sample Input 2

4

Sample Output 2

230

Sample Input 3

100

Sample Output 3

388130742

Be sure to print the number of strings modulo 10^9+7.



Sample input:
3


Sample output:
61

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import re
from itertools import product

atcg = ['A', 'T', 'C', 'G']
num = int(input())

def validate(tpl):
    string = tpl[0] + tpl[1] + tpl[2] + tpl[3]
    for pat in [r'A.GC', r'AG.C', 'ACG', 'AGC', 'GAC']:
         if re.search(pat, string):
                return False
    return True

def transition(dic):
    new_dic = defaultdict(int)
    for k, v in dic.items():
        for c in atcg:
            tpl = *k[1:], c
            if validate(tpl):
                new_dic[tpl] += v
    return new_dic

it = product(atcg, atcg, atcg, atcg)
dic = {}
for s in it:
    if validate(s):
        dic[s] = 1

if num == 3:
    print(61)
elif num == 4:
    print(230)
else:
    for n in range(num - 4):
        dic = transition(dic)
    print(sum(dic.values()) % 1000000007)

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split(" ")))
s = input()
s = s.replace("AC", "ZC")
ac_index = [s[:i].count("Z") for i in range(len(s))]
i = 0

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = input()

A = ('A', 'C', 'G', 'T')

array = []
dellist = []


for i in itertools.product(A, repeat=N):
  array.append(i)

for j in range(len(array)):
  if ('AGC' in array) or ('GAC' in array) or ('ACG' in array):
    dellist.append(array[j])

print((len(array)-len(dellist)) % 1000000007)

Submission status: Runtime Error

Solution code:
N = int(input())

A = ('A', 'C', 'G', 'T')

array = []
dellist = []


for i in itertools.product(A, repeat=N):
  array.append(i)

for j in range(len(array)):
  if ('AGC' in array) or ('GAC' in array) or ('ACG' in array):
    dellist.append(array[j])

print(len(array)-len(dellist))

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
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;
}

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
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;
}

Submission status: Runtime Error

Solution code:
from functools import lru_cache
MOD = 1000_000_007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

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

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


for L in range(N):
    for i in range(4):
        
        for j in range(4):
        
            for k in range(4):
                if (dp[L][i][j][k]==0): continue
                for a in range(4):
                    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[L+1][a][i][j] += dp[L][i][j][k]
                    dp[L+1][a][i][j] %= modd
  
ans = 0         
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= modd
print(ans)

Submission status: Runtime Error

Solution code:
#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;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll MOD = 1000000007;

int main(void){
    int N;
    cin >> N;
    vector<vector<vector<vector<ll>>>> dp(N+1,vector<vector<vector<ll>>>(4,vector<vector<ll>>(4, vector<ll>(4,0))));
    int A=0,C=1,G=2,T=3;
    // AGC / GAC / ACG / AXGC / AGXC がダメ
    dp[0][3][3][3] = 1;
    for (int len = 0; len < N; len++){
        for (int i = 0; i < 4; i++){
            for (int j = 0; j < 4; j++){
                for (int k = 0; k < 4; k++){
                    if (dp[len][i][j][k] == 0) continue;
                    
                    for (int a = 0; a < 4; a++){
                        if (a == C && i == G && j == A) continue;
                        if (a == C && i == A && j == G) continue;
                        if (a == G && i == C && j == A) continue;
                        if (a == C && i == G && k == A) continue;
                        if (a == C && j == G && k == A) continue;
                        
                        dp[len + 1][a][i][j] += dp[len][i][j][k];
                        dp[len + 1][a][i][j] %= MOD;
                    }
                }
            }
        }
    }
    
    ll ans = 0;
    
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            for (int k = 0; k < 4; k++){
                ans += dp[N][i][j][k];
                ans %= MOD;
            }
        }
    }
    
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
using namespace std;

int MOD = 1000000007;

int main(void){
    int N;
    cin >> N;
    vector<vector<vector<vector<int>>>> dp(N+1,vector<vector<vector<int>>>(4,vector<vector<int>>(4, vector<int>(4,0))));
    int A=0,C=1,G=2,T=3;
    // AGC / GAC / ACG / AXGC / AGXC がダメ
    dp[0][3][3][3] = 1;
    for (int len = 0; len < N; len++){
        for (int i = 0; i < 4; i++){
            for (int j = 0; j < 4; j++){
                for (int k = 0; k < 4; k++){
                    if (dp[len][i][j][k] == 0) continue;
                    
                    for (int a = 0; a < 4; a++){
                        if (a == C && i == G && j == A) continue;
                        if (a == C && i == A && j == G) continue;
                        if (a == G && i == C && j == A) continue;
                        if (a == C && i == G && k == A) continue;
                        if (a == C && j == G && k == A) continue;
                        
                        dp[len + 1][a][i][j] += dp[len][i][j][k];
                        dp[len + 1][a][i][j] %= MOD;
                    }
                }
            }
        }
    }
    
    int ans = 0;
    
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            for (int k = 0; k < 4; k++){
                ans += dp[N][i][j][k];
                ans %= MOD;
            }
        }
    }
    
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(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(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if check(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    print(memo)
    return ret

print(dfs(0, 'TTT'))

Submission status: Runtime Error

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

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

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

print(dfs(0, 'TTT'))

Submission status: Runtime Error

Solution code:
N = int(input())
dp = [[[[0 for l in range(4)] for k in range(4)]
       for j in range(4)] for i in range(N)]
for j in range(4):
    for k in range(4):
        for l in range(4):
            if not (j == 0 and k == 1 and l == 2)\
                    and not(j == 0 and k == 2 and l == 1)\
                    and not (j == 2 and k == 0 and l == 1):
                dp[2][j][k][l] = 1
for i in range(2, N-1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] %= 10**9+7
                dp[i+1][k][l][0] += dp[i][j][k][l]
                # 0123: ACGT
                # AG?
                # ?GA
                # A?G
                # ?AG
                if not (j == 0 and k == 2) \
                   and not (k == 2 and l3 == 0)\
                   and not (j == 0 and l == 2)\
                   and not (k == 0 and l == 2):
                    dp[i+1][k][l][1] += dp[i][j][k][l]
                # ?AC
                if not (k == 0 and l == 1):
                    dp[i+1][k][l][2] += dp[i][j][k][l]
                dp[i+1][k][l][3] += dp[i][j][k][l]
ans = 0
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[N-1][j][k][l]
ans %= 10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
dp = [ [ [ [0] * 4 ] * 4 ] * 4 ] * 101
'''
長さ0の文字列は1
0, 1, 2に関する制約しかないので、Sは、333Sと考えても問題がない
'''
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)

Submission status: Runtime Error

Solution code:
N = int(input())

dp = [[0 for i in range(16)] for j in range(N)]
dp2 = [[0 for j in range(4)] for j in range(N)]
for i in range(16):
    dp[1][i] = 1

for i in range(2, N):

    DP = dp[i - 1]
    dp[i][0] = DP[0] + DP[4] + DP[8] + DP[12]
    dp[i][1] = DP[0] + DP[4] + DP[8] + DP[12]
    dp[i][2] = DP[0] + DP[8] + DP[12]
    dp[i][3] = DP[0] + DP[4] + DP[8] + DP[12]
    dp[i][4] = DP[1] + DP[5] + DP[9] + DP[13]
    dp[i][5] = DP[1] + DP[5] + DP[9] + DP[13]
    dp[i][6] = DP[5] + DP[9] + DP[13]
    dp[i][7] = DP[1] + DP[5] + DP[9] + DP[13]
    dp[i][8] = DP[2] + DP[6] + DP[10] + DP[14]
    dp2[i][0] = DP[6] + DP[10] + DP[14]
    dp[i][9] = DP[6] + DP[10] + DP[14] - dp2[i - 1]
    dp2[i][1] = DP[]
    dp[i][10] = DP[2] + DP[6] + DP[10] + DP[14]
    dp[i][11] = DP[2] + DP[6] + DP[10] + DP[14]
    dp[i][12] = DP[3] + DP[7] + DP[11] + DP[15]
    dp[i][13] = DP[3] + DP[7] + DP[11] + DP[15]
    dp[i][14] = DP[3] + DP[7] + DP[11] + DP[15]
    dp2[i] = DP[3]
    dp[i][15] = DP[3] + DP[7] + DP[11] + DP[15]

print(sum(dp[-1]) % (10 ** 9 + 7))
print(dp)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def memo_rec(N):
    if N == 3:
        return 61
    L = ['A', 'T', 'G', 'C']
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(l1, l2, l3, k):
        s = l1 + l2 + l3
        if s in ["AGC", "ACG", "GAC"]:
            return 0
        if k == 1:
            if (l1 == 'A' and l2 == 'C') or (l1 == 'C' and l2 == 'G') or (l1 == 'G' and l3 == 'C') or (l2 == 'G' and l3 == 'C') or (l1 == 'G' and l2 == 'C'):
                return 3
            else:
                return 4
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(x, l1, l2, k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 3):
        ret = (ret + rec(s[0], s[1], s[2], N - 3)) % MOD
    return ret

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

Submission status: Runtime Error

Solution code:
import itertools

def memo_rec(N):
    L = ['A', 'T', 'G', 'C']
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(l1, l2, l3, k):
        s = l1 + l2 + l3
        if s in ["AGC", "ACG", "GAC"]:
            return 0
        if k == 1:
            if (l1 == 'A' and l2 == 'C') or (l1 == 'C' and l2 == 'G') or (l1 == 'G' and l3 == 'C') or (l2 == 'G' and l3 == 'C') or (l1 == 'G' and l2 == 'C'):
                return 3
            else:
                return 4
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(x, l1, l2, k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 3):
        ret = (ret + rec(s[0], s[1], s[2], N - 3)) % MOD
    return ret

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

Submission status: Runtime Error

Solution code:
N = input()
X = 16*(N-4)*4**(N-5)+2*(N-2)*4*(N-3)
A = (4**N-X)%(10**9+7)
print(A)

Submission status: Runtime Error

Solution code:
N = int(input())
ans = [1, 4, 16]
for i in range(3, 100):
  ans[i] = 61 * ans[i-3]
print(ans[N-1] % )

Submission status: Runtime Error

Solution code:
n=int(input())
mod=10**9+7
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%=mod
        ans*=4
        ans%=mod
        for j in range(len(z)):
            z=[]
            for k in range(4):
                f=0
                s=z[j][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
                    z+=[s]
    print(ans%mod)

Submission status: Runtime Error

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

dp = [61]
for i in range(3, N):
    num = dp[-1]
    dp.append((4*num-15**(len(dp)))-2*(4**(len(dp)-1)))%mod)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import math

def nCm(n,m):
    return math.factorial(n) / (math.factorial(m)*(math.facorial(n-m)))

n = int(input())
kinds = 4**n
a = 7 + 10**9
answer = 0
q = 0
r = 0

p = 3 * nCm(n-2, 1)
if n > 6:
    q = 3 * nCm(n-4, 2)
if n > 9:    
    r = nCm(n-6, 3)

answer = (kinds - p + q -r) % a

print(int(answer))

Submission status: Runtime Error

Solution code:
n = int(input())
all = 4^n
if n ==2:
  print("61")
elif n ==3*
  print("230")
else: print("22")

Submission status: Runtime Error

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

#print(N,Q,S)

L = S.replace('AC', '1 0 ').replace('T', '0 ').replace('G', '0 ')
R = S.replace('AC', '0 1 ').replace('T', '0 ').replace('G', '0 ')

L = list( map(int, L.split()) )	# 1 2 3 4 5 ...
R = list( map(int, R.split()) )	# 1 2 3 4 5 ...

#L = [1,2,3,4,5,6,7,8,9]
#R = [1,2,3,4,5,6,7,8,9]
#print(N,Q,S,L,R)
#print(N,Q,S)
#print("L", L)
#print("R", R)


from functools import reduce
#print( reduce(lambda x,y: x+y, L) )	#=> 10 (=sum(1,2,3,4))


for q in range(1,Q+1):
	ans=0
	l, r = map(int, input().split())		# 5 7

	X=L[l-1:l]
	Y=R[l+1:r]
	Z=X+Y+[0]
	
	ans = reduce(lambda x,y: x+y, Z)	#=> 10 (=sum(1,2,3,4))

	#print(l,r,"X=",X,"Y=",Y,"Z=",Z,ans)

	print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0, 0, 0, 61, 230, 853, 3123, 11316, 40652, 144996, 514041, 1812978, 6365809, 22265835]

print(A[N] % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
n=int(input())
ans=61
for i in range(n-3):
    ans*=4
    ans-=14
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
mod=10**9+7
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
        ans%=mod
        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%mod)

Submission status: Runtime Error

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

# 1整数
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')

##後ろ4文字を与えて，それがokかどうか
def isok(str):
    if str[-4:] in out:
        return False
    return True


#N文字で最後の4文字がstrの時の種類数
@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))
#print('len is ',len(strlist))
rr = 0
for strs in strlist:
    rr += saiki(n,''.join(strs))
print(rr%divide)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
import itertools
import re


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix


def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix


def makeInt(line):
    return int(line.rstrip())


def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

dp = {}

def solve(input_string):
    S = input_string[1]
    intMatrix = makeIntMatrix(input_string[2:])
    #print(input_string[2:])
    for line in intMatrix:
        l, r = line
        #print(l, r)
        #print(S[l:r+1])
        #cnt = len(re.findall(r'AC', S[l-1:r]))
        cnt = cntAC(l, r, S[l-1:r])
        print(cnt)
    return


def cntAC(l, r, t):
    if l+r is not dp:
        dp[l+r] = len(re.findall(r'AC', t))
    return dp[l+r]


def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    #print(answer)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
# input = sys.stdin.readline
# def ii(): return int(input())
# def mi(): return map(int, input().rstrip().split())
# def lmi(): return list(map(int, input().rstrip().split()))
# def li(): return list(input().rstrip())
# # template


N, Q = map(int, sys.stdin.readline().rstrip().split())
S = list(sys.stdin.readline().rstrip())
Alist = []
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = map(int, sys.stdin.readline().rstrip().split())
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        Alist.append(i)
AClist = [0]*(N+1)
for i in range(N - 1):
    if i in Alist:
        AClist[i + 2] = AClist[i+1] + 1
    else:
        AClist[i+2] = AClist[i+1]

# print(AClist)

for i in range(Q):
    if AClist[l[i] - 1] != AClist[l[i]]:
        print(AClist[r[i]] - AClist[l[i]])
    else:
        print(AClist[r[i]] - AClist[l[i]-1])