Пробовал но безуспешно ( нужен фулл код на питоне )

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

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

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

Первая строка входных данных содержит одно целое число N (1 ≤ N ≤ 109).

Входные данные: 4 Выходные данные: 18