Олимпиадная задача, оптимизация кода

Есть олимпиадная задачка, её суть такова: Дано целое число 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.