В одной биоинженерной компании по непонятной причине отказали все скрипты. Так что генетики исследуют последовательности нуклеотидов вручную. Чтобы легче передавать информацию…

Для решения этой задачи мы можем использовать комбинаторный подход, чтобы вычислить количество "читаемых" последовательностей длины \( N \), которые соблюдают указанные условия.

Определим правила формирования читаемых последовательностей:

1. Гласные: A, G (здесь считаем G гласной для данного контекста).
2. Согласные: T, C.

Для создания читаемой последовательности длины \( N \), необходимо следить за тем, чтобы:

• Ни одна согласная не следовала за другой согласной.
• Ни одна гласная не следовала за другой гласной.

Это означает, что последовательности должны чередоваться между гласными и согласными. Таким образом, возможные комбинации для каждой позиции могут выглядеть следующим образом:

• Если на i-ой позиции стоит гласная (A или G), то i+1-ая позиция должна быть согласной (T или C).
• Если на i-ой позиции стоит согласная (T или C), то i+1-ая позиция должна быть гласной (A или G).

Можно ввести две переменные:

• \( f[n] \): количество читаемых последовательностей длиной \( n \) с гласной на последнем месте.
• \( g[n] \): количество читаемых последовательностей длиной \( n \) с согласной на последнем месте.

Мы можем записать рекуррентные соотношения:

• \( f[n] = 2 \cdot g[n-1] \) (если на i-ой позиции гласная, предыдущая должна быть согласной, всего 2 варианта гласных).
• \( g[n] = 2 \cdot f[n-1] \) (если на i-ой позиции согласная, предыдущая должна быть гласной, всего 2 варианта согласных).

Теперь составим общее количество читаемых последовательностей длиной \( n \): \[ total[n] = f[n] + g[n] \]

Начальные значения:

• Для \( n = 1 \):
  • \( f[1] = 2 \) (A, G)
  • \( g[1] = 2 \) (T, C)

Теперь можем рассчитать значения для \( n \) от 2 до заданного \( N \):

def readable_sequences_count(N):
    if N == 1:
        return 4  # 2 гласные + 2 согласные

    f = [0] * (N + 1)
    g = [0] * (N + 1)

    f[1] = 2  # A, G
    g[1] = 2  # T, C

    for n in range(2, N + 1):
        f[n] = 2 * g[n - 1]
        g[n] = 2 * f[n - 1]

    total = (f[N] + g[N]) % (10**9 + 7)
    return total

# Пример вызова функции
N = int(input("Введите N: "))  # Запросите значение N
print(readable_sequences_count(N))

Обратите внимание, что результаты выводятся по модулю \( 10^9 + 7 \), поскольку количество последовательностей может быть очень большим.