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

Чтобы решить эту задачу, нужно понять, что читаемая последовательность состоит из символов A, G, T и C. При этом символы A и G являются согласными, а T и C — гласными. Условие задачи гласит, что рядом не могут находиться две одной согласной (т.е. AA или GG), и рядом не могут находиться две одной гласной (т.е. TT или CC).

Таким образом, можно использовать динамическое программирование для подсчета количества читаемых последовательностей.

1. Обозначим:

   • f(n) — количество читаемых последовательностей длины n.
   • c(n) — количество читаемых последовательностей длины n, заканчивающихся на согласную.
   • v(n) — количество читаемых последовательностей длины n, заканчивающихся на гласную.

2. Рекуррентные соотношения:

   • f(n) = c(n) + v(n)
   • c(n) = v(n-1) * 2 (Если последовательность заканчивается на согласную, перед ней должна быть гласная, и она может быть T или C.)
   • v(n) = c(n-1) * 2 (Если последовательность заканчивается на гласную, перед ней должна быть согласная, и она может быть A или G.)

3. Начальные условия:

   • f(1) = 4 (A, G, T, C)
   • c(1) = 2 (A, G)
   • v(1) = 2 (T, C)

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

MOD = 10**9 + 7

def count_readable_sequences(N):
    if N == 1:
        return 4
        
    c = [0] * (N + 1)
    v = [0] * (N + 1)

    # Начальные условия
    c[1] = 2  # A, G
    v[1] = 2  # T, C

    for n in range(2, N + 1):
        c[n] = v[n-1] * 2 % MOD  # Две согласные
        v[n] = c[n-1] * 2 % MOD  # Две гласные

    f = (c[N] + v[N]) % MOD
    return f

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

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