Ускорение программы Python

В одной биоинженерной компании по непонятной причине отказали все скрипты.

Так что генетики исследуют последовательности нуклеотидов вручную. Чтобы легче передавать информацию устно, они называют последовательность символов A, G, T, C «читаемой», если рядом ни с одной согласной нет другой согласной, а рядом ни с одной гласной — другой гласной, и предпочитают работать только с такими последовательностями.

Дано число N. Сколько различных читаемых последовательностей длины N существует? Так как ответ может быть очень большим, выведите остаток от его деления на 109 + 7.

Далее моя программа, она проходит только 23 теста из 40, ошибка TL. Кто знает как можно ее ускорить? Попробовал заменить деление и mod на другие операции, добавить функции, которые вроде как занимают меньше времени, но все равно по времени не проходит (1 сек)

N (1 ≤ N ≤ 10**9)

if int(N * 0.5) == N * 0.5:  
    print(int(int((3 ** int(N * 0.5)) * 2) % 1000000007))
else:
    print(int(int(4 * (3 ** int((N - 1) * 0.5))) % 1000000007))