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:
N = int(input())
ACGT = []

def get_ACGT(S, n):
  if len(S) >= 3:
    for i in range(len(S) - 2):
      if S[i : i + 3] == "AGC" or S[i : i + 3] == "ACG" or S[i : i + 3] == "GAC":
        return 0
  if len(S) >= 4:
    for i in range(len(S) - 1):
      if S[i : i + 4] == "AGGC" or S[i : i + 4] == "ATGC" or S[i : i + 4] == "AGGC" or S[i : i + 4] == "AGTC":
        return 0
  if len(S) == n:
    return 1
  return get_ACGT(S + "A", n) + get_ACGT(S + "C", n) + get_ACGT(S + "G", n) + get_ACGT(S + "T", n)

for i in range(N - 2):
  if i <= 3:
    ACGT.append(get_ACGT("", i + 3))
  else:
    ACGT.append(ACGT[i - 1] * 4 - ACGT[i - 3] * 3 - ACGT[i - 4] * 4)

print(ACGT[N - 3] % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    sum = 61
    for i in range(4, N + 1):
        counter = i
        # start A
        a = sum - 2 * 4 ** (counter - 3) - 2 * 4 ** (counter - 4)
        if counter > 5:
            a -= 2
        # start C
        c = sum
        # start G
        g = sum - 4 ** (counter - 3)
        # start T
        t = sum
        sum = a + c + g + t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

    num = num_now.copy()


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

Submission status: Wrong Answer

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9 + 7

N=ri()
dp = [[[0 for k in range(4)] for j in range(7)] for i in range(N)]
dp[0][0][0] = 2
dp[0][1][0] = 1
dp[0][5][0] = 1

for i in range(1,N):
    dp[i][0][0] = dp[i-1][0][0]*2 + dp[i-1][2][2] + dp[i-1][3][2] + dp[i-1][4][1]*2 + dp[i-1][5][0]*2 + dp[i-1][5][1] + dp[i-1][6][1]*2 + dp[i-1][6][2]
    dp[i][1][0] = dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][2] + dp[i-1][4][1] + dp[i-1][5][1] + dp[i-1][6][1] 
    dp[i][1][1] = dp[i-1][1][0] + dp[i-1][5][1]
    dp[i][1][2] = dp[i-1][1][1]
    dp[i][2][2] = dp[i-1][1][1]
    dp[i][2][3] = dp[i-1][2][2]
    dp[i][3][2] = dp[i-1][1][1]
    dp[i][3][3] = dp[i-1][3][2]
    dp[i][4][1] = dp[i-1][1][0]
    dp[i][4][2] = dp[i-1][4][1]
    dp[i][5][0] = dp[i-1][0][0] + dp[i-1][2][2] + dp[i-1][3][2] + dp[i-1][5][0] + dp[i-1][6][2]
    dp[i][5][1] = dp[i-1][1][1] + dp[i-1][3][2] + dp[i-1][5][0] + dp[i-1][6][2]
    dp[i][5][2] = dp[i-1][5][1]
    dp[i][6][1] = dp[i-1][1][0]
    dp[i][6][2] = dp[i-1][6][1]
    dp[i][6][3] = dp[i-1][6][2]

ans = dp[N-1][0][0] + dp[N-1][1][0] + dp[N-1][1][1] + dp[N-1][2][2] + dp[N-1][3][2] + dp[N-1][4][1] + dp[N-1][5][0] + dp[N-1][5][1] + dp[N-1][6][1] + dp[N-1][6][2]

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
print(4**n- (n-2)*3**3*4**(n-2))

Submission status: Wrong Answer

Solution code:
from itertools import product
n=int(input())
List=["A","C","G","T"]
count=0
for p in product("ACGT",repeat=n):
    count+=1
    if "AGC" in "".join(p):count-=1
    elif "ACG" in "".join(p):count-=1
    elif "GAG" in "".join(p):count-=1
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=3
count=4**N-3*8**N-2*(N-3)
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())

P=10**9+7

dpin=[0]*100
dpno=[0]*100

dpno[0]=4
dpno[1]=16
dpno[2]=61
dpno[3]=230

dpin[2]=3
dpin[3]=26


for i in range(4,N):
    dpin[i]=(dpin[i-1]*4+dpno[i-3]*14)%P
    dpno[i]=(pow(4,i+1,P)-dpin[i])%P


print(dpno[N-1])

Submission status: Wrong Answer

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

#   1
#   A    A    ACGT
#        C    AC-T
#        G    A-GT
#        T    ACGT
#   C
#   G 
#   T    A
#        C
#        G    AG-T
#        T
#  ACG
#  AGC
#  GAC
#
# A?GC
#  AG?C
#         A  T  G  C
#            G  G
#            G  T

dp = [[0 for j in range(4)] for i in range(N+1)]
A=0
C=1
G=2
T=3

i=0
dp[i][A]=dp[i][C]=dp[i][G]=dp[i][T]=1
#print(dp[i])

i=1
dp[i][A]=dp[i][C]=dp[i][G]=dp[i][T]=4
#print(dp[i])

i=2
s=sum(dp[i-1])
dp[i][A]=s
dp[i][C]=s-dp[i-2][A]-dp[i-2][G]
dp[i][G]=s-dp[i-2][A]
dp[i][T]=s
#print(dp[i])

for i in range(3,N+1):
    s=sum(dp[i-1])
    dp[i][A]=s
    dp[i][C]=s-dp[i-2][A]-dp[i-2][G]-dp[i-3][A]*3
    dp[i][G]=s-dp[i-2][A]
    dp[i][T]=s
    #print(dp[i])

print(sum(dp[N-1]) % mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N = int(input())
	
	total = runEXP(4, N)
	if N == 3:
		tmp = ((3  * (N-2)) + ((N-3)*2)) % 1000000007
	else:
		tmp = runEXP(3, (N))  % 1000000007
	
	print(total - tmp)
			
def runEXP(N, P):
	if P == 0:
		return 1
	if P == 1:
		return N
	if P == 2:
		return N * N
	else:
		if P % 2 == 0:
			tmp = runEXP(N, P // 2)
			return  (tmp % 1000000007) * (tmp % 1000000007)
		else:
			P -= 1
			tmp = runEXP(N, P // 2)
			return  (tmp % 1000000007) *  (tmp % 1000000007) * N
			
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())

def count(s):
    if len(s) == N:
        return 1
    if len(s) >= 2 and (s[-2:] == 'AG' or s[-2:] == 'AC' or s[-2:] == 'GA'):
        return count(s + 'A') + count(s + 'G') + count(s + 'T')
    elif len(s) > 2 and s[-3] == 'A' and s[-1] == 'G':
        return count(s + 'A') + count(s + 'G') + count(s + 'T')
    elif len(s) > 2 and s[-3] == 'A' and s[-2] == 'G':
        return count(s + 'A') + count(s + 'G') + count(s + 'T')
    else:
        return count(s + 'A') + count(s + 'G') + count(s + 'T') + count(s + 'C')


print(count(''))

Submission status: Wrong Answer

Solution code:
N = int(input())
# ACGTのみで作る
# AGCの並びが出ない
# 2文字入れ替えてもAGCにならない
#3:AGC, GAC, ACG
#4:ATGC, AGTC, AGGC

diff = N - 3
ng3 = 3
if diff > 0:
    ng3 = 3 * (4**diff)*(N-2) - (4**(N-4))*(N-3) - (4**(N-5))*(N-4)

diff = N - 4
ng4 = 0
if diff == 0:
    ng4 = 3
if diff > 0:
    ng4 = 3 * (4**diff) - (3 * (N//4)**(N%4))

print((4**N - ng3 - ng4)%(10**9+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Submission status: Wrong Answer

Solution code:
N = int(input())

if N == 3:
  print("61")
  exit()
DP=[1, 4, 16, 61, 230]
MOD = 10 ** 9 + 7

for i in range(4, N):
  x = DP[i] * 4
  x -= DP[i - 2] * 2
  x -= DP[i - 3] * 5
  while x < 0:
    x += MOD
  DP.append(x % MOD)

print(DP[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]*N
G = [0]*N
C = [0]*N
A[0] = 1
A[1] = 3
A[2] = 7
G[0] = 1
G[1] = 3
G[2] = 8
C[0] = 1
C[1] = 3
C[2] = 9

for i in range(4,N+1):
    j = i-1
    A[j] = A[j-1]+A[j-2]+C[j-2]+1
    G[j] = G[j-1]+C[j-1]+1
    C[j] = A[j-3]+G[j-1]+C[j-1]+C[j-3]+1
    for k in range(2,i):
        if k % 2 == 0:
            A[j] += A[j-k]
            G[j] += A[j-k]
            C[j] += A[j-k]
        else:
            A[j] += G[j-k]
            G[j] += G[j-k]
            C[j] += G[j-k]


print((4**N-3**N+A[N-1]+G[N-1]+C[N-1])%(10**9+7))

Submission status: Wrong Answer

Solution code:
n=int(input())
x=(4**n)%(10**9+7)
y=(3*(n-2))%(10**+7)
print(x-y)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import math
import re

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    if N == 3:
        print 61
        return

    X = N - 3
    ans = 1L
    for i in range(N):
        ans = (ans * 4L) % 1000000007L
    sub = 26L
    for i in range(X -1):
        sub = (sub * 4L) % 1000000007L

    print (ans - sub) % 1000000007L





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
dp=[[0]*16 for _ in range(N+1)]
for i in range(16):
    dp[2][i]=1
for n in range(3,N+1):
    for f in range(4):
        for s in range(4):
            if f==0 and s==1:
                dp[n][s*4+0]=(dp[n][s*4+0]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+1]=(dp[n][s*4+1]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+3]=(dp[n][s*4+3]+dp[n-1][f*4+s])%(10**9+7)
            elif f==0 and s==2:
                dp[n][s*4+0]=(dp[n][s*4+0]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+2]=(dp[n][s*4+2]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+3]=(dp[n][s*4+3]+dp[n-1][f*4+s])%(10**9+7)
            elif f==2 and s==0:
                dp[n][s*4+0]=(dp[n][s*4+0]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+2]=(dp[n][s*4+2]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+3]=(dp[n][s*4+3]+dp[n-1][f*4+s])%(10**9+7)
            else:
                dp[n][s*4+0]=(dp[n][s*4+0]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+1]=(dp[n][s*4+1]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+2]=(dp[n][s*4+2]+dp[n-1][f*4+s])%(10**9+7)
                dp[n][s*4+3]=(dp[n][s*4+3]+dp[n-1][f*4+s])%(10**9+7)
print(sum(dp[N])%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())

S = 'ACGT'
#n[a][b][c][i]=number of abc[i] 0=A 1=C 2=G 3=T
n = [[[[1] for c in range(4)] for b in range(4)] for a in range(4)]
n[0][3][2][0] = 0
n[2][0][1][0] = 0
n[0][1][2][0] = 0

N -= 3
for i in range(N):
    for add in range(4):
        for P in range(4):
            for Q in range(4):
                t = 0
                for O in range(4):
                    if add == 1:
                        if P == 0 and Q == 2: continue#_AGC
                        if O == 0 and Q == 2: continue#A_GC
                        if O == 0 and P == 2: continue#AG_C
                        if P == 2 and Q == 0: continue#_GAC
                    if add == 2:
                        if P == 0 and Q == 1: continue#_ACG
                    t += n[O][P][Q][i]

                n[P][Q][add].append(t)
print(
    sum(
        [n[a][b][c][N] for a in range(4) for b in range(4) for c in range(4)]
        )
    %(10**9+7)
    )

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    sum = 61
    for i in range(4, N + 1):
        counter = i
        # start A
        a = sum - 2 * 4 ** (counter - 3) - 2 * 4 ** (counter - 4)
        # start C
        c = sum
        # start G
        g = sum - 4 ** (counter - 3)
        # start T
        t = sum
        sum = a + c + g + t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ACGT = []

def get_ACGT(S, n):
  if len(S) >= 3:
    for i in range(len(S) - 2):
      if S[i : i + 3] == "AGC" or S[i : i + 3] == "ACG" or S[i : i + 3] == "GAC":
        return 0
  if len(S) >= 4:
    for i in range(len(S) - 1):
      if S[i : i + 4] == "AGGC" or S[i : i + 4] == "ATGC" or S[i : i + 4] == "AGGC" or S[i : i + 4] == "AGTC":
        return 0
  if len(S) == n:
    return 1
  return get_ACGT(S + "A", n) + get_ACGT(S + "C", n) + get_ACGT(S + "G", n) + get_ACGT(S + "T", n)

for i in range(N - 2):
  if i == 0:
    ACGT.append(61)
  elif i == 1:
    ACGT.append(230)
  elif i == 2:
    ACGT.append(get_ACGT("", 5))
  elif i == 3:
    ACGT.append(get_ACGT("", 6))
  else:
    ACGT.append(ACGT[i - 1] * 4 - ACGT[i - 3] * 3 - ACGT[i - 4] * 4)

print(ACGT[N - 3] % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
# 2019/03/24
# AtCoder Beginner Contest 122 - D

# Input
n = int(input())

ans = (4**n - ((n-1)**(n-1) - 1)) % (10**9 + 7)

# Output
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

mod = 10 ** 9 + 7

def question():
    n = int(input())

    a = [0] * (n+1)
    a[1] = 1
    a[2] = 4
    a[3] = 16

    t = [0] * (n+1)
    t[1] = 1
    t[2] = 4
    t[3] = 16

    c = [0] * (n+1)
    c[1] = 1
    c[2] = 4
    c[3] = 14

    g = [0] * (n+1)
    g[1] = 1
    g[2] = 4
    g[3] = 15

    for i in range(3, n):
        a[i + 1] = a[i] + t[i] + c[i] + g[i]
        t[i + 1] = a[i] + t[i] + c[i] + g[i]
        c[i + 1] = a[i] + t[i] + c[i] + g[i] - (a[i-1] + 2 * a[i-2] + g[i-1])
        g[i + 1] = a[i] + t[i] + c[i] + g[i] - (a[i-1])

        a[i+1] = a[i+1] % mod
        t[i+1] = t[i+1] % mod
        c[i+1] = c[i+1] % mod
        g[i+1] = g[i+1] % mod

    print(a[n]+t[n]+c[n]+g[n])


question()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N = int(input())
	
	total = runEXP(4, N)
	if N == 3:
		tmp = ((3  * (N-2)) + ((N-3)*2)) % 1000000007
	else:
		tmp = ((3 * N * (N-2)) + ((N-3)*2)) % 1000000007
	
	print(total - tmp)
			
def runEXP(N, P):
	if P == 0:
		return 1
	if P == 1:
		return N
	if P == 2:
		return N * N
	else:
		if P % 2 == 0:
			tmp = runEXP(N, P // 2)
			return  (tmp % 1000000007) * (tmp % 1000000007)
		else:
			P -= 1
			tmp = runEXP(N, P // 2)
			return  (tmp % 1000000007) *  (tmp % 1000000007) * N
			
if __name__ == "__main__":
	main()

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-1][8]+res[i-1][9]
    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)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    sum = 61
    for i in range(4, N + 1):
        counter = i
        # start A
        a = sum - 2 * 4 ** (counter - 3)
        if counter > 3:
            a -= 2 * 4 ** (counter - 4)
        # start C
        c = sum
        # start G
        g = sum - 4 ** (counter - 3)
        # start T
        t = sum
        sum = a + c + g + t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

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

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    sum = 61
    for i in range(4, N + 1):
        counter = i
        # start A
        a = sum - 2 * 4 ** (counter - 3)
        if counter > 3:
            a -= 2 * 4 ** (counter - 4)
        print(a)
        # start C
        c = sum
        # start G
        g = sum - 4 ** (counter - 3)
        print(g)
        # start T
        t = sum
        sum = a + c + g + t

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

print( (4**N-( (2*(N-2)*pow(4,N-3) + (2*(N-3)*pow(4,N-3)) \
    -9*(max(0,N-4)) -2*(max(0,N-5)) -2*(max(0,N-6)) + N-2) ) )%mod )

Submission status: Wrong Answer

Solution code:
MOD = int(10**9 + 7)
N = int(input())
cnt = [4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 4, 4]
for i in range(N-3):
    c = [0 for _ in range(16)]
    for j in range(16):
        if j == 0:
            c[0] += cnt[0]
            c[1] += cnt[0]
            c[2] += cnt[0]
            c[3] += cnt[0]
        elif j == 1:
            c[4] += cnt[1]
            c[5] += cnt[1]
            c[7] += cnt[1]
        elif j == 2:
            c[8] += cnt[2]
            c[9] += cnt[2]
            c[11] += cnt[2]
        elif j == 3:
            c[12] += cnt[3]
            c[13] += cnt[3]
            c[14] += cnt[3]
            c[15] += cnt[3]
        elif j == 4:
            c[4] += cnt[4]
            c[5] += cnt[4]
            c[6] += cnt[4]
            c[7] += cnt[4]
        elif j == 5:
            c[0] += cnt[5]
            c[1] += cnt[5]
            c[3] += cnt[5]
        elif j == 6:
            c[8] += cnt[6]
            c[9] += cnt[6]
            c[10] += cnt[6]
            c[11] += cnt[6]
        elif j == 7:
            c[12] += cnt[7]
            c[13] += cnt[7]
            c[14] += cnt[7]
            c[15] += cnt[7]
        elif j == 8:
            c[8] += cnt[8]
            c[9] += cnt[8]
            c[10] += cnt[8]
            c[11] += cnt[8]
        elif j == 9:
            c[0] += cnt[9]
            c[1] += cnt[9]
            c[2] += cnt[9]
            c[3] += cnt[9]
        elif j == 10:
            c[4] += cnt[10]
            c[5] += cnt[10]
            c[6] += cnt[10]
            c[7] += cnt[10]
        elif j == 11:
            c[12] += cnt[11]
            c[13] += cnt[11]
            c[14] += cnt[11]
            c[15] += cnt[11]
        elif j == 12:
            c[12] += cnt[12]
            c[13] += cnt[12]
            c[14] += cnt[12]
            c[15] += cnt[12]
        elif j == 13:
            c[0] += cnt[13]
            c[1] += cnt[13]
            c[2] += cnt[13]
            c[3] += cnt[13]
        elif j == 14:
            c[4] += cnt[14]
            c[5] += cnt[14]
            c[6] += cnt[14]
            c[7] += cnt[14]
        elif j == 15:
            c[8] += cnt[15]
            c[9] += cnt[15]
            c[10] += cnt[15]
            c[11] += cnt[15]
    for j in range(16):
        c[j] = c[j] % MOD
    cnt = c[:]
print(sum(cnt) % MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
count = 4**N - 3*(N-2)*(4**(N-3))

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

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(1,N+1):
#    res[i][0] = sum(res[i-1]) - res[i-1][2] - res[i-1][4] - res[i-1][8]
#    res[i][1] = sum(res[i-1]) - res[i-1][0] - res[i-1][4] - res[i-1][6] - res[i-1][7] - res[i-1][8]
#    res[i][2] = sum(res[i-1]) - res[i-1][0] - res[i-1][4] - res[i-1][6] - res[i-2][0]*4 - res[i-1][5]
#    res[i][3] = sum(res[i-1])               - res[i-1][4]
#    res[i][4] = res[i-1][0] + res[i-1][6]
#    res[i][5] = res[i-1][0] + res[i-1][6]
#    res[i][6] = res[i-1][2] + res[i-1][4] + res[i-1][8]
#    res[i][7] = res[i-1][4]*3
#    res[i][8] = res[i-2][0]*4

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-1][8]+res[i-1][9]
    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]))

Submission status: Wrong Answer

Solution code:
import sys

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

num = 10 ** 9 + 7
n = int(input())
li = {3:3}
base = 4 ** n
def calc(n):
    if n ==3:
        return 3
    else:
        return calc(n-1) * 8 + 2 
print((base-calc(n))%num)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())
if n>3:
    print((4**n-3*cmb(n-2,1)*4**(n-3)-(n-3)- cmb(n,4) )%(10**9+7))
else:
    print(61)

Submission status: Wrong Answer

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

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(4,101):
  dp[i]=(4*dp[i-1]-14*dp[i-4])%p
print(dp[100])

Submission status: Wrong Answer

Solution code:
n = int(input())
s = ['A', 'C', 'G', 'T']
list = []
cnt = 0
for h in range(10**4):
  for i in range(3):
    for j in range(3):
      for k in range(3):
        for l in range(3):
          l = s[i]+s[j]+s[k]+s[l]
  list.append(l)
for i in range(n):
  if 'AGC' in list[i]:
    cnt += 1
print((4**3-cnt)/(10**9+7))

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())
#print(3*cmb(n-2,n-3)*4**(n-3))
print((4**n-3*cmb(n-2,1)*4**(n-3)- (n-3)*2 )%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
ACGT = []

def get_ACGT(S, n):
  if len(S) >= 3:
    for i in range(len(S) - 2):
      if S[i : i + 3] == "AGC" or S[i : i + 3] == "ACG" or S[i : i + 3] == "GAC":
        return 0
  if len(S) >= 4:
    for i in range(len(S) - 1):
      if S[i : i + 4] == "AGGC" or S[i : i + 4] == "ATGC" or S[i : i + 4] == "AGAC" or S[i : i + 4] == "AGGC" or S[i : i + 4] == "AGTC":
        return 0
  if len(S) == n:
    return 1
  return get_ACGT(S + "A", n) + get_ACGT(S + "C", n) + get_ACGT(S + "G", n) + get_ACGT(S + "T", n)

for i in range(N - 2):
  if i == 0:
    ACGT.append(61)
  elif i == 1:
    ACGT.append(230)
  elif i == 2:
    ACGT.append(get_ACGT("", 5))
  elif i == 3:
    ACGT.append(get_ACGT("", 6))
  else:
    ACGT.append(ACGT[i - 1] * 4 - ACGT[i - 3] * 3 - ACGT[i - 4] * 5)

print(ACGT[N - 3] % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
n = int(input())

if n == 3:
    print(61)
else:
    ans = 4**n*230**(n-3)//256**(n-3)
    ans = int(ans)
    print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10**9+7
if N == 3:
    ans = 61
else:
    ans = 4 ** N - (6 * 4 ** (N - 3) + 2 * 4 ** (N - 4))

print(ans % 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[13]
  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
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

print( (4**N-( (2*(N-2)*pow(4,N-3) + (2*(N-3)*pow(4,N-3)) \
    -9*(max(0,N-4)) + N-2) ) )%mod )

Submission status: Wrong Answer

Solution code:
def least_AGC_num(num):
    if num <= 2:
        return 0
    return 4 ** (num - 3) * (num - 2)


def no_AGC_num(num):
    return 4 ** num - least_AGC_num(num)


def no_AGC_and_not_edge_num(num):
    return 4 ** (num - 1) * 3 - least_AGC_num(num)


N = int(input())

pattern_num = 4 ** N
least_AGC = least_AGC_num(N)
# print(pattern_num)
# print(least_AGC_num(N))
# print()
exchange_AGC = 0
for idx in range(N - 2):
    left_pattern = no_AGC_num(idx)
    right_pattern = no_AGC_num(N - 3 - idx)
    # print(left_pattern)
    # print(right_pattern)
    exchange_AGC = exchange_AGC + (right_pattern * left_pattern) * 2
    if idx != 0:
        exchange_AGC = exchange_AGC + no_AGC_and_not_edge_num(idx)
    if N - 3 - idx != 0:
        exchange_AGC = exchange_AGC + no_AGC_and_not_edge_num(N - 3 - idx)
    exchange_AGC = exchange_AGC % (10 ** 9 + 7)
    # print()
print((pattern_num - least_AGC - exchange_AGC) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()

print( (4**N-( (2*(N-2)*pow(4,N-3) + (2*(N-3)*pow(4,N-3)) \
    -9*(max(0,N-4)) + N-2) ) ) )

Submission status: Wrong Answer

Solution code:
import math
length = int(input())
all = 4**length
warusu = 10**9+7
output_num = (4**all-math.factorial(length-2)*3)%warusu

print(output_num)

Submission status: Wrong Answer

Solution code:
r = 1e9 + 7
def dp(n):
    if n == 3:
        return 61
    return (dp(n-1) * 4 * 230 / 244) % r


n = int(input())
print(int(dp(n)))

Submission status: Wrong Answer

Solution code:
import math
length = int(input())
all = 4**length
output_num = 4**all-math.factorial(length-2)*3

print(output_num)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N = int(input())
a = [[1,1,1,1]]
a.append([4,4,4,4])
a.append([16,15,14,16])
for i in range(N - 3):
  b = [0,0,0,0]
  b[0] = (sum(a[-1][:])) % (10 ** 9 + 7)
  b[1] = (sum(a[-1][:]) - a[-2][0] - a[-3][0] * 2) % (10 ** 9 + 7)
  b[2] = (sum(a[-1][:]) - a[-2][1] - a[-2][0]) % (10 ** 9 + 7)
  b[3] = b[0]
  a.append(b)
#print(a)
print(sum(a[-1][:]))

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N = int(input())
a = [[1,1,1,1]]
a.append([4,4,4,4])
a.append([16,15,14,16])
for i in range(N - 3):
  b = [0,0,0,0]
  b[0] = (sum(a[-1][:])) % (10 ** 9 + 7)
  b[1] = (sum(a[-1][:]) - a[-2][0]) % (10 ** 9 + 7)
  b[2] = (sum(a[-1][:]) - a[-2][1] - a[-2][0] - a[-3][0] * 2) % (10 ** 9 + 7)
  b[3] = b[0]
  a.append(b)
#print(a)
print(sum(a[-1][:]))

Submission status: Wrong Answer

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)):
            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
    print(ans%mod)