Numerele lui Catalan formează un șir cunoscut în combinatorică. Termenul general al acestui șir este:

$$C_n = C_{2n}^{n} – C_{2n}^{n+1} = \frac{1}{n+1}\cdot C_{2n}^{n} = \prod _{k=2}^{n} \frac{n+k}{k}, \text{pentru } n ≥ 0$$

Primele $10$ numere Catalan sunt: $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862$

Cerința

Se dă numărul natural n. Să se determine și să se afișeze al n-lea număr Catalan.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran al n-lea număr Catalan.

Restricții și precizări

• 0 ≤ n ≤ 1000

Exemplu:

Intrare

5

Ieșire

42