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: Wrong Answer

Solution code:
import numpy as np

def main():
    N = int(input())
    dp = [[[[0 for _ in range(4)]for _ in range(4)]for _ in range(4)]for _ in range(N+1)]
    #ndp = np.array(dp)
    #print(ndp.shape)
    dp[0][3][3][3] = 1

    for len in range(N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    if dp[len][c1][c2][c3] == 0:
                        continue
                    for a in range(4):#次に最後尾につく数
                        if a == 2 and c1 == 1 and c2 == 0:
                            continue
                        if a == 2 and c1 == 0 and c2 == 1:
                            continue
                        if a == 1 and c1 == 2 and c2 == 0:
                            continue
                        if a == 2 and c1 == 1 and c3 == 0:
                            continue
                        if a == 2 and c2 == 1 and c3 == 0:
                            continue

                        #ダメな条件を超えたので足してよい
                        dp[len+1][a][c1][c2] += dp[len][c1][c2][c3]
                        dp[len+1][a][c1][c2] %= 1000000007
    ans = 0
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                ans += dp[N][c1][c2][c3]

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())

def swap(a,b):
    c=[i for i in a]
    c[b],c[b+1]=c[b+1],c[b]
    return "".join(c)

def ok(a):
    if "AGC" in swap(a,0) or "AGC" in swap(a,1) or "AGC" in swap(a,2) or "AGC" in a:
        return False
    return True

if n==1:
    print(4)
elif n==2:
    print(16)
else:
    a={}
    for i in "ACGT":
        for j in "ACGT":
            for k in "ACGT":
                if not i+j+k in ["AGC","ACG","CGA"]:
                    a[i+j+k]=1
    for q in range(n-3):
        b={}
        for i in a:
            for j in "ACGT":
                if ok(i+j):
                    w=i[1:]+j
                    if w in b:
                        b[w]+=a[i]
                    else:
                        b[w]=a[i]
        a=dict(b)
    al=0
    for i in a:
        al+=a[i]
    print(al%(10**9+7))

Submission status: Wrong Answer

Solution code:
def pow_mod(a: int, n: int, mod: int)->int:
    ret = 1
    for _ in range(n):
        ret = (ret * a) % mod
    return ret


def ok(s: str)->bool:
    if 'GAC' == s:
        return False
    if 'ACG' == s:
        return False
    if 'A' == s[0] and 'GC' == s[-2:]:
        return False
    if 'AG' == s[:2] and 'C' == s[-1]:
        return False
    return True


def we_like_agc(N: int)->int:
    MOD = 10**9 + 7
    AGCT = 'AGCT'

    # dp[i][str] は str の出現回数。
    dp = [{}, {}]

    # dp の初期化
    for c1 in AGCT:
        for c2 in AGCT:
            for c3 in AGCT:
                dp[0][c1 + c2 + c3] = 1 if ok(c1 + c2 + c3) else 0
                dp[1][c1 + c2 + c3] = 0

    turn = 0
    for _ in range(3, N):
        next_turn = 1-turn
        for s, v in dp[turn].items():
            for c in AGCT:
                next_word = s[1:] + c
                if ok(s + c):
                    dp[next_turn][next_word] += v
                    dp[next_turn][next_word] %= MOD
            dp[turn][s] = 0
        # print(dp[0])
        # print(dp[1])
        turn = next_turn

    # print(dp)

    return sum(v for s, v in dp[(N+1) & 1].items() if ok(s)) % MOD


if __name__ == "__main__":
    N = int(input())
    ans = we_like_agc(N)
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

MOD = 1000000000 + 7
N=int(input())
dp = [{} for i in range(N+1)]
dp[0] = {"TTT":1}

# 終わりではない
def ok(l):
    r = True
    r = r and not "AGC" in l
    r = r and not "AGC" in l[1]+l[0]+l[2]+l[3]
    r = r and not "AGC" in l[0]+l[2]+l[1]+l[3]
    r = r and not "AGC" in l[0]+l[1]+l[3]+l[2]
    return r

# 最後の3つが決まると，わかる
for i in range(N):
    for key in dp[i]:
        for c in "ATCG":
            s = key+c
            if ok(s):
                new_key = s[1:4]
                if not new_key in dp[i+1]:
                    dp[i+1][new_key] = dp[i][key] % MOD
                else:
                    dp[i+1][new_key] = (dp[i+1][new_key]+dp[i][key]) % MOD
                    

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

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

MOD = 1000000000 + 7
N=int(input())
dp = [{} for i in range(N+1)]
dp[0] = {"TTT":1}

# 終わりではない
def ok(l):
    r = True
    r = r and not "AGC" in l
    r = r and not "AGC" in l[1]+l[0]+l[2]+l[3]
    r = r and not "AGC" in l[0]+l[2]+l[1]+l[3]
    r = r and not "AGC" in l[0]+l[1]+l[3]+l[2]
    return r

# 最後の3つが決まると，わかる
for i in range(N):
    for key in dp[i]:
        for c in "ATCG":
            s = key+c
            if ok(s):
                new_key = s[1:4]
                if not new_key in dp[i+1]:
                    dp[i+1][new_key] = dp[i][key]
                else:
                    dp[i+1][new_key] += dp[i][key]

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

print(cnt)

Submission status: Wrong Answer

Solution code:
# 参考：https://twitter.com/tempura_cpp/status/1109812850820698112

from sys import stdin

# 各文字を分かりやすいようにintで
A = 0
G = 1
C = 2
T = 3

# mod定義
mod = 10**9 + 7

# 3 <= N <= 100
N = int(stdin.readline().rstrip())

# dp[101][4][4][4]の初期化
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(101)]


"""
# ダメな条件
AGC(012)
GAC(102)
ACG(021)
A?GC(0?12)
AG?C(01?2)

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

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

for i in range(N):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for a in range(4):
                    # ダメな条件の時は処理しない
                    if c2 == A and c3 == G and a == C: continue # AGC
                    if c2 == G and c3 == A and a == C: continue # GAC
                    if c2 == A and c3 == C and a == G: continue # ACG
                    if c1 == A and c3 == G and a == C: continue # A?GC
                    if c1 == A and c2 == G and a == C: continue # AG?C
                    
                    # 足し込む
                    # 例えば ?TAC の4文字の数は ATA, GTA, CTA, TTA の3文字の集合の総数
                    # ただ、上でダメな条件はcontinueしてるので含まれない
                    dp[i+1][c2][c3][a] += dp[i][c1][c2][c3] % mod

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np

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

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

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

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

print(func(0,""))

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
N = int(input())
memo = [{} for _ in range(N + 1)]

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

def dfs(last3, n):
  if last3 in memo[n]:
    return memo[n][last3]
  if n == N:
    return 1
  ret = 0
  for c in "AGCT":
    if ok(last3 + c):
      ret += dfs(last3[1:] + c, n + 1) % (10 ** 9 + 7)
  memo[n][last3] = ret
  return ret

print(dfs("TTT", 0))

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = [{} for _ in range(N + 1)]

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

def dfs(last3, n):
  if last3 in memo[n]:
    return memo[n][last3]
  if n == N:
    return 1
  ret = 0
  for c in "AGCT":
    if ok(last3 + c):
      ret += dfs(last3[1:] + c, n + 1)
  memo[n][last3] = ret
  return ret

print(dfs("TTT", 0) % (10 ** 9 + 7))

Submission status: Wrong Answer

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


dp=[dict() for i in range(m)]
cnt=[0]*m
for s in d4:
    dp[3][s]=1
    

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

#print(len(kinsoku4),kinsoku4)
#print(dp)

#for x in cnt:
    #print(x%mo)

if n==3:
    ans=63
    print(ans)
else:
    print(cnt[n-1])
#print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 1000000007
p = [0]*(n+1)
p[0] = 0
p[1] = 0
p[2] = 0

memo_a ={}
memo_g ={}


def c(i):
  return p[i-1]

def t(i):
  return p[i-1]

def a(i):
  ans = 0
  if i-1>=0:
    ans += p[i-1]

  if i ==3:
    ans +=1
  elif i-4>=0: #AGC
    if i-3 not in memo_a:
      memo_a[i-3] = a(i-3)
    if i-3 not in memo_g:
      memo_g[i-3] = g(i-3)
    ans += 2*(4**(i-4)-p[i-4]) + ((4**(i-4)-p[i-4]) - memo_a[i-3]) + ((4**(i-4)-p[i-4]) - memo_g[i-3])

  if i ==3:
    ans +=1
  elif i-4>=0: #ACG
    if i-3 not in memo_g:
      memo_g[i-3] = g(i-3)
    ans += 2*(4**(i-4)-p[i-4]) + ((4**(i-4)-p[i-4]) - memo_g[i-3])
  if i-5>=0: #ACG
    if i-3 not in memo_a:
      memo_a[i-4] = a(i-4)
    ans += (4**(i-5)-p[i-5]) +((4**(i-5)-p[i-5]) - memo_a[i-4]) 

  if i ==4:#AG*C or A*GC
    ans += 4
  elif i-5>=0: #AG*C or A*GC
    ans += (4**(i-5) - p[i-5])*4*4
  return  ans

def g(i):
  if i<=2:
    return 0
  elif i ==3:
    return 1
  else:
    if i-3 not in memo_a:
      memo_a[i-3] = a(i-3)
    return p[i-1] + 2*(4**(i-4)-p[i-4]) + ((4**(i-4)-p[i-4]) - memo_a[i-3])
  
for i in range(3,n+1):
  p[i] += c(i)+ t(i)+ g(i)+ a(i)
  p[i] = p[i]%mod

toori = 1
for i in range(n):
  toori *= 4
  toori %=mod 
#print(toori,p[n])
print( (toori - p[n])%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import product
import numpy as np

def main():
    N = II()
    A, G, C, T = 0, 1, 2, 3
    dp = np.zeros((N + 1, 4, 4, 4), int)
    dp[0, T, T, T] = 1
    for n in range(N):
        for p1, p2, p3 in product(range(4), repeat=3):
            for cur in range(4):
                if (p2, p1, cur) == (A, G, C):
                    continue
                if (p2, p1, cur) == (A, C, G):
                    continue
                if (p2, p1, cur) == (G, A, C):
                    continue
                if (p3, p1, cur) == (A, G, C):
                    continue
                if (p3, p2, cur) == (A, G, C):
                    continue
                dp[n + 1, cur, p1, p2] += dp[n, p1, p2, p3]
    ans = np.sum(dp[N])

    return ans % MOD

print(main())

Submission status: Wrong Answer

Solution code:
N = input()

T = [[[0]*4 for i in range(4)] for j in range(4)]
for c1 in range(4):
  for c2 in range(4):
    for c3 in range(4):
      if (0, 1, 2) not in [
        (c1, c2, c3),
        (c2, c1, c3),
        (c1, c3, c2),
      ]:
        T[c1][c2][c3] = 1

for i in range(3, N):
  P = T
  T = [[[0]*4 for i in range(4)] for j in range(4)]
  for c1 in range(4):
    for c2 in range(4):
      for c3 in range(4):
        for c4 in range(4):
          if (0, 1, 2) not in [
            (c2, c3, c4),
            (c3, c2, c4),
            (c2, c4, c3),
            (c1, c3, c4),
            (c1, c2, c4),
          ]:
            T[c2][c3][c4] += P[c1][c2][c3]
            T[c2][c3][c4] %= 1000000007
print sum(sum(sum(t2) for t2 in t1) for t1 in T)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def check(s):
    c = False
    if s[:3] == "AGC" or s[1:] == "AGC" or s[0] + s[2:] == "AGC" or s[:2] + s[3] == "AGC" or s[:3] == "ACG" or s[1:] == "ACG" or s[:3] == "GAC" or s[1:] == "GAC":
        c = True
    return c

from collections import defaultdict
from itertools import product
N = int( input())
Q = 10**9 + 7
dp = [ defaultdict( int) for _ in range(N+1)]

for s in product("AGCT", repeat = 3):
    dp[3]["".join(s)] = 1
ans = 0
for i in range(4, N+1):
    for c in product("AGCT", repeat = 3):
        c = "".join(c)
        for t in "AGCT":
            if check(c+t):
                # print(c+t, dp[i-1][c])
                ans += (dp[i-1][c]*pow(4,i-4,Q))%Q
                ans %= Q
            else:
                dp[i][c[1:]+t] += dp[i-1][c]
                dp[i][c[1:]+t] %= Q
if N == 3:
    ans = 3
print( (pow(4,N,Q) - ans)%Q)

Submission status: Wrong Answer

Solution code:
def check(s):
    c = False
    if s[:3] == "AGC" or s[1:] == "AGC" or s[0] + s[2:] == "AGC" or s[:2] + s[3] == "AGC" or s[:3] == "ACG" or s[1:] == "ACG" or s[:3] == "GAC" or s[1:] == "GAC":
        c = True
    return c

from collections import defaultdict
from itertools import product
N = int( input())
Q = 10**9 + 7
dp = [ defaultdict( int) for _ in range(N+1)]

for s in product("AGCT", repeat = 3):
    dp[3]["".join(s)] = 1
ans = 0
for i in range(4, N+1):
    for c in product("AGCT", repeat = 3):
        c = "".join(c)
        for t in "AGCT":
            if check(c+t):
                print(c+t, dp[i-1][c])
                ans += (dp[i-1][c]*pow(4,i-4,Q))%Q
                ans %= Q
            else:
                dp[i][c[1:]+t] += dp[i-1][c]
                dp[i][c[1:]+t] %= Q
if N == 3:
    ans = 3
print( (pow(4,N,Q) - ans)%Q)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = [None, None, 61, 230]
for _ in range(N-4):
    ans.append(ans[-1]*4-12)
print(ans[-1] % (10**9+7))

Submission status: Wrong Answer

Solution code:
N=int(input())
MOD=10**9+7
a=[[0 for i in range(64)] for j in range(101)]
a[3]=[1 for i in range(101)]
a[3][6],a[3][9],a[3][18]=0,0,0
for i in range(4,N+1):
  a[i][0]=(a[i-1][0]+a[i-1][16]+a[i-1][32]+a[i-1][48])%MOD
  a[i][1]=a[i][0]
  a[i][2]=a[i][0]
  a[i][3]=a[i][0]
  a[i][4]=(a[i-1][1]+a[i-1][17]+a[i-1][33]+a[i-1][49])%MOD
  a[i][5]=a[i][4]
  a[i][6]=0
  a[i][7]=a[i][4]
  a[i][8]=(a[i-1][2]+a[i-1][18]+a[i-1][34]+a[i-1][50])%MOD
  a[i][9]=0
  a[i][10]=a[i][8]
  a[i][11]=a[i][8]
  a[i][12]=(a[i-1][3]+a[i-1][19]+a[i-1][35]+a[i-1][51])%MOD
  a[i][13]=a[i][12]
  a[i][14]=a[i][12]
  a[i][15]=a[i][12]
  a[i][16]=(a[i-1][4]+a[i-1][20]+a[i-1][36]+a[i-1][52])%MOD
  a[i][17]=a[i][16]
  a[i][18]=0
  a[i][19]=a[i][16]
  a[i][20]=(a[i-1][5]+a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][21]=a[i][20]
  a[i][22]=(a[i-1][21]+a[i-1][37]+a[i-1][53])%MOD
  a[i][23]=a[i][20]
  a[i][24]=(a[i-1][6]+a[i-1][22]+a[i-1][38]+a[i-1][54])%MOD
  a[i][25]=a[i][24]
  a[i][26]=a[i][24]
  a[i][27]=a[i][24]
  a[i][28]=(a[i-1][7]+a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][29]=a[i][28]
  a[i][30]=(a[i-1][23]+a[i-1][39]+a[i-1][55])%MOD
  a[i][31]=a[i][28]
  a[i][32]=(a[i-1][8]+a[i-1][24]+a[i-1][40]+a[i-1][56])%MOD
  a[i][33]=a[i][32]
  a[i][34]=a[i][32]
  a[i][35]=a[i][32]
  a[i][36]=(a[i-1][9]+a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][37]=a[i][36]
  a[i][38]=(a[i-1][25]+a[i-1][41]+a[i-1][57])%MOD
  a[i][39]=a[i][36]
  a[i][40]=(a[i-1][10]+a[i-1][26]+a[i-1][42]+a[i-1][58])%MOD
  a[i][41]=a[i][40]
  a[i][42]=a[i][40]
  a[i][43]=a[i][40]
  a[i][44]=(a[i-1][11]+a[i-1][27]+a[i-1][43]+a[i-1][59])%MOD
  a[i][45]=a[i][44]
  a[i][46]=a[i][44]
  a[i][47]=a[i][44]
  a[i][48]=(a[i-1][12]+a[i-1][28]+a[i-1][44]+a[i-1][60])%MOD
  a[i][49]=a[i][48]
  a[i][50]=a[i][48]
  a[i][51]=a[i][48]
  a[i][52]=(a[i-1][13]+a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][53]=a[i][52]
  a[i][54]=(a[i-1][29]+a[i-1][45]+a[i-1][61])%MOD
  a[i][55]=a[i][52]
  a[i][56]=(a[i-1][14]+a[i-1][30]+a[i-1][46]+a[i-1][62])%MOD
  a[i][57]=a[i][56]
  a[i][58]=a[i][56]
  a[i][59]=a[i][56]
  a[i][60]=(a[i-1][15]+a[i-1][31]+a[i-1][47]+a[i-1][63])%MOD
  a[i][61]=a[i][60]
  a[i][62]=a[i][60]
  a[i][63]=a[i][60]
print(sum(a[N])%MOD)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 10**9+7
a = [1]*16
no = [0,0]
for _ in range(n-2):
  b = [0]*16
  b[0] = a[0] + a[4] + a[8] + a[12]
  b[1] = a[0] + a[4] + a[12]
  b[2] = a[0] + a[4] + a[8] + a[12]
  b[3] = a[0] + a[4] + a[8] + a[12]
  b[4] = a[1] + a[5] + a[9] + a[13]
  b[5] = a[1] + a[5] + a[9] + a[13]
  b[6] = a[5] + a[9] + a[13]
  b[7] = a[1] + a[5] + a[9] + a[13]
  b[8] = a[2] + a[6] + a[9] + a[14]
  b[9] = a[6] + a[9] + a[14] - no[0] - no[1]
  b[10] = a[2] + a[6] + a[9] + a[14]
  b[11] = a[2] + a[6] + a[9] + a[14]
  b[12] = a[3] + a[7] + a[10] + a[15]
  b[13] = a[3] + a[7] + a[10] + a[15] - no[1]
  b[14] = a[3] + a[7] + a[10] + a[15]
  b[15] = a[3] + a[7] + a[10] + a[15]
  no[0] = a[2]
  no[1] = a[3]
  a = b
  for i in range(16):
    a[i] %= mod
print(sum(a))

Submission status: Wrong Answer

Solution code:
import itertools

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: Wrong Answer

Solution code:
N = int(input())

print(4 ** N - 3 * (4 **(N-3) ) * (N-2))

Submission status: Wrong Answer

Solution code:
N = int(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: Wrong Answer

Solution code:
import collections as c
ip = lambda : map(int, input().split())

#################
N = int(input())
mod = 1000000007
A=0
T=1
C=2
G=3
dp = [[[[0,0,0,0] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]

for j in range(4):
    for k in range(4):
        for l in range(4):
            dp[3][j][k][l] = 1
dp[3][A][G][C],dp[3][A][C][G],dp[3][G][A][C] = 0,0,0

for i in range(4,N+1):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[i][j][k][l] += (dp[i-1][A][j][k]+dp[i-1][T][j][k]+dp[i-1][C][j][k]+dp[i-1][G][j][k]) % mod
                dp[i][j][k][l] %= mod



    dp[i][A][G][C],dp[i][A][C][G],dp[i][G][A][C] = 0,0,0

    dp[i][T][G][C] = max(0,dp[i][T][G][C] - dp[i-1][A][T][G])

    dp[i][G][G][C] = max(0,dp[i][G][G][C] - dp[i-1][A][G][G])
    #dp[i][G][A][C] -= dp[i-1][A][G][A]
    dp[i][G][T][C] = max(0,dp[i][G][T][C] - dp[i-1][A][G][T])

r = 0
for j in range(4):
    for k in range(4):
        r += sum(dp[N][j][k])
        r %= mod
print(r%mod)

Submission status: Wrong Answer

Solution code:
dp = [0 for i in range(0, 101)]
dp[3] = 61
dp[4] = 230

for i in range(5, 101):
    dp[i] = (4 * dp[i - 1] - 14 * (1<<2*(i-4)))

N = int(input())
print(dp[N]%1000000007)

Submission status: Wrong Answer

Solution code:
N = int(input())

sub_arr = [3]
one = 1
two = 2
for i in range(4,101):
    one = one * 8 * (1+(N-4))
    two = (8 * two) - (two - 1) + 3
    sub_arr.append(one+two) 

print(4**N-sub_arr[N-3])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 20:52:46 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

"""

N = int(input())
dp = [0]*N
dp[0] = 4
dp[1] = 15
dp[2] = 61
if N == 3:
    print(dp[2])
    sys.exit()
dp[3] = 230
for n in range(4, N):
    dp[n] = dp[n-1] + dp[n-1]-dp[n-3] + dp[n-1]-dp[n-3] + dp[n-1]
    
res = dp[N-1]
print(res%(10**(9)+7))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


# inputs
N = 0


def set_inputs():
    global N
    N = get_int()
    return


DIVISOR = 1000000007


def main():
    setrecursionlimit(100000)
    set_inputs()

    # ACG, AGC, GAC, AGGC, AGTC, ATGC
    safe = [0] * N
    a = [0] * N
    g = [0] * N
    ac = [0] * N
    ag = [0] * N
    at = [0] * N
    ga = [0] * N
    agg = [0] * N
    agt = [0] * N
    atg = [0] * N

    safe[0] = 1
    for i in range(1, N):
        s = safe[i-1] * 2
        s += g[i-1] * 2
        s += ac[i-1] * 2
        s += ga[i-1]
        s += at[i-1]
        s += agg[i-1]
        s += agt[i-1]
        s += atg[i-1]
        safe[i] = s % DIVISOR

        a_ = safe[i-1]
        a_ += a[i-1]
        a_ += ac[i-1]
        a_ += at[i-1]
        a_ += ga[i-1]
        a_ += agt[i-1]
        a[i] = a_ % DIVISOR

        g_ = safe[i-1]
        g_ += g[i-1]
        g_ += ga[i-1]
        g_ += agg[i-1]
        g_ += agt[i-1]
        g_ += atg[i-1]
        g[i] = g_ % DIVISOR

        ac[i] = a[i-1] % DIVISOR
        ag[i] = (a[i-1] + ga[i-1]) % DIVISOR
        at[i] = (a[i-1] + ga[i-1]) % DIVISOR
        ga[i] = (g[i-1] + ag[i-1] + agg[i-1] + atg[i-1]) % DIVISOR
        agg[i] = ag[i-1] % DIVISOR
        agt[i] = ag[i-1] % DIVISOR
        atg[i] = at[i-1] % DIVISOR

        dead = (ac[i-1] + ag[i-1] + ga[i-1] + agg[i-1] + agt[i-1] + atg[i-1]) % DIVISOR
    print(safe[N-1] + a[N-1] + g[N-1] + ac[N-1] + ag[N-1] + at[N-1] + ga[N-1] + agg[N-1] + agt[N-1] + atg[N-1])
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


# inputs
N = 0


def set_inputs():
    global N
    N = get_int()
    return


DIVISOR = 1000000007


def main():
    setrecursionlimit(100000)
    set_inputs()

    # ACG, AGC, GAC, AGGC, AGTC, ATGC
    safe = [0] * N
    a = [0] * N
    g = [0] * N
    ac = [0] * N
    ag = [0] * N
    at = [0] * N
    ga = [0] * N
    agg = [0] * N
    agt = [0] * N
    atg = [0] * N

    safe[0] = 1
    for i in range(1, N):
        s = safe[i-1] * 2
        s += g[i-1] * 2
        s += ac[i-1] * 2
        s += ga[i-1]
        s += at[i-1]
        s += agg[i-1]
        s += agt[i-1]
        s += atg[i-1]
        safe[i] = s

        a_ = safe[i-1]
        a_ += a[i-1]
        a_ += ac[i-1]
        a_ += at[i-1]
        a_ += ga[i-1]
        a_ += agt[i-1]
        a[i] = a_

        g_ = safe[i-1]
        g_ += g[i-1]
        g_ += ga[i-1]
        g_ += agg[i-1]
        g_ += agt[i-1]
        g_ += atg[i-1]
        g[i] = g_

        ac[i] = a[i-1]
        ag[i] = a[i-1] + ga[i-1]
        at[i] = a[i-1] + ga[i-1]
        ga[i] = g[i-1] + ag[i-1] + agg[i-1] + atg[i-1]
        agg[i] = ag[i-1]
        agt[i] = ag[i-1]
        atg[i] = at[i-1]

        dead = ac[i-1] + ag[i-1] + ga[i-1] + agg[i-1] + agt[i-1] + atg[i-1]
    print(safe[N-1] + a[N-1] + g[N-1] + ac[N-1] + ag[N-1] + at[N-1] + ga[N-1] + agg[N-1] + agt[N-1] + atg[N-1])
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

sub_arr = [3]
one = 1
two = 2
for i in range(4,101):
    one = one * 8 * (2+(N-4))
    two = (8 * two) - (two - 1) + 3
    sub_arr.append(one+two) 

print(4**N-sub_arr[N-3])

Submission status: Wrong Answer

Solution code:
dp=[0]*101
dp[3]=61
dp[4]=230
dp[5]=863
dp[6]=3230
p=10**9 +7
for i in range(4,101):
  dp[i]=(4*dp[i-1]-14*dp[i-4])%p
n=int(input())
print(dp[n])

Submission status: Wrong Answer

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