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
((())), ()(()), ()()(), (())(), (()()).