Editing 3990 - Dinamica 09

==Cerința==
Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula modulo 123457.

==Date de intrare==
Programul citește de la tastatură numărul n,.

==Date de ieșire==
Programul va afișa pe ecran numărul cerut, modulo 123457.

Restricții și precizări
Pentru 80 de puncte, 1 ≤ n ≤ 10.000
Pentru alte 20 de puncte, 100.000.000 ≤ n ≤ 1.000.000.000
==Exemplu==:
Intrare

2
Ieșire

6
==Explicație==
Numerele sunt 12, 14, 24, 32, 34, 42.
==Rezolvare==
def count_numbers(n):
    mod = 123457

    # Inițializare vector dp
    dp = [[0] * 4 for _ in range(n + 1)]
    for i in range(1, 4):
        dp[1][i] = 1

    # Calcul numărul de numere
    for i in range(2, n + 1):
        dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod
        dp[i][3] = (dp[i - 1][1] + dp[i - 1][2]) % mod

    result = (dp[n][1] + dp[n][2] + dp[n][3]) % mod
    return result

# Citire date de intrare
n = int(input())

# Calcul și afișare rezultat
result = count_numbers(n)
print(result)