mirror of
https://github.com/codeflash-ai/codeflash-internal.git
synced 2026-05-04 18:25:18 +00:00
54 lines
1,016 B
Python
54 lines
1,016 B
Python
def problem_p03088(input_data):
|
|
from collections import defaultdict
|
|
from itertools import product
|
|
|
|
MOD = 10**9 + 7
|
|
|
|
N = int(eval(input_data))
|
|
|
|
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
|
|
|
|
A = 0
|
|
C = 1
|
|
G = 2
|
|
T = 3
|
|
|
|
cur = defaultdict(lambda: 1)
|
|
|
|
cur[(A, G, C)] = cur[(G, A, C)] = cur[(A, C, G)] = 0
|
|
|
|
for _ in range(3, N):
|
|
|
|
prev = cur
|
|
|
|
cur = defaultdict(int)
|
|
|
|
for i, j, k, l in product(list(range(4)), repeat=4):
|
|
|
|
if (
|
|
(j, k, l) == (A, G, C)
|
|
or (j, k, l) == (G, A, C)
|
|
or (i, k, l) == (A, G, C)
|
|
or (i, j, l) == (A, G, C)
|
|
or (j, k, l) == (A, C, G)
|
|
):
|
|
|
|
continue
|
|
|
|
else:
|
|
|
|
cur[(j, k, l)] += prev[(i, j, k)]
|
|
|
|
for ijk in product(list(range(4)), repeat=3):
|
|
|
|
cur[ijk] %= MOD
|
|
|
|
ans = sum(cur.values()) % MOD
|
|
|
|
if N <= 3:
|
|
|
|
return [1, 4, 16, 61][N]
|
|
|
|
else:
|
|
|
|
return ans
|