Non-Intersecting Chords on a Circle

Given a circle with 2N distinct points placed on its circumference, you are to connect these points using exactly N non-intersecting chords such that each point is connected by exactly one chord. Determine the total number of ways to form such a configuration.

The solution to this problem is given by the Catalan numbers. In particular, for a given integer N, the number of ways is the Nth Catalan number, which can be computed using the recurrence:

[ C(0)=1, \quad C(n)=\sum_{i=0}^{n-1}C(i)\cdot C(n-1-i) \quad \text{for } n\ge1. ]

inputFormat

The input contains a single integer N (1 ≤ N ≤ 50) on one line, representing the number of chords to draw (and hence there are 2N points on the circle).

outputFormat

Output a single integer: the number of ways to connect the 2N points with N non-intersecting chords.

sample

1

1