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

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