How many instances of "е" are there in:
Q: Олимпиадная задача, оптимизация кода Есть олимпиадная задачка, её суть такова:
Дано целое число 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.

A: Проблема в том, что при возведении в степень получается уж очень большое число. Однако оно нам нужно не само по себе, а остаток от деления по указанному модулю. Поэтому можно использовать быстрое бинарное возведение в степень по модулю, в ходе работы которого длинные числа появляться не будут. На ваше счастье, в Python есть готовая функция - это pow с третьим аргументом.
Формулы ваши, кстати, можно упростить
2*3**(n//2)
4*3**(n//2)

Пример для чётной части, время мгновенное
n = 8888888888
m = pow(3, n//2, 1000000007)
result = (m + m) % 1000000007
print(result)


user
I found ninety-one "е"s in the provided passage.
assistant