1257 - NumarParanteze

Cerința

Să se determine numărul de șiruri de lungime 2 * n care conțin paranteze închise corect.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran restul împărțirii numărului de șiruri de lungime 2 * n, care sunt parantezate corect, la 666013.

Restricții și precizări

• 1 ≤ n ≤ 1000

Exemplu

Intrare

3

Ieșire

5

Explicație

((())), ()(()), ()()(), (())(), (()()).

Rezolvare

def numar_siruri_parantezate_corect(n):
    MOD = 666013
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        for j in range(i):
            dp[i] = (dp[i] + dp[j] * dp[i - 1 - j]) % MOD

    return dp[n]

# Citire date de intrare
n = int(input("Introduceți n: "))

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