Есть олимпиадная задачка, её суть такова: Дано целое число N. 1 <= N <= 10^9. Необходимо определить количество возможных последовательностей длины N, составленных из символов A, G, T, C при условии, что согласные и гласные буквы в этих последовательностях должны чередоваться. Так как ответ может быть очень большим, вывести его остаток от деления на (10^9 + 7). Ограничение по времени - 1 секунда.
Есть переборное решение, которое проходит тесты с N < 11:
import itertools
n = int(input())
s = "AGTC"
count = 0
for i in itertools.product(s, repeat=n):
word = "".join(i)
flag = True
if word[0] == "A":
for ind in range(0, len(word), 2):
if not word[ind] == "A":
flag = False
break
for ind in range(1, len(word), 2):
if not flag: break
if not word[ind] in "GTC":
flag = False
break
if word[0] in "GTC":
for ind in range(0, len(word), 2):
if not flag: break
if not word[ind] in "GTC":
flag = False
break
for ind in range(1, len(word), 2):
if not flag: break
if not word[ind] == "A":
flag = False
break
if flag:
count += 1
print(count)
Проанализировав закономерность в ответах, были определены формулы, которые позволят вычислить ответ за 1 сек. для значений N < 10^4:
n = int(input())
if n % 2 == 0:
result = 6 * 3 ** (n // 2 - 1)
else:
result = 4 * 3 ** ((n - 1) // 2)
print(result % (10**9 + 7))
Нужна помощь с нахождением решения, которое не будет превышать лимит времени 1 сек. для N до 10^9.