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

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

#include <bits/stdc++.h>
using namespace std;
#define MOD 666013
unsigned long long a[1001] , n;

int main()
{
    cin >> n;
    a[0] = 1;
    a[1] = 1;
    for(int i = 2; i <= n ; ++i)
        for(int j = 0; j < i ; ++j)
            a[i] = (a[i] + (a[j] * a[i - j - 1])) % MOD;
    cout << a[n] % MOD;
    return 0;
}