Catalan Ticket Queue

In a historic football match, there is an enormous queue of fans waiting to buy a ticket. Each ticket costs $50. There are 2n fans in total: n fans holding a 50-dollar bill (denoted by A) and n fans holding a 100-dollar bill (denoted by B). The ticket booth starts with no change. In order to serve every fan without running into a shortage of change, at any point in the queue the number of A-type fans must be no less than the number of B-type fans.

This problem is equivalent to counting the number of valid sequences of A's and B's, where a valid sequence always has at least as many A's as B's in every prefix. Mathematically, this is given by the Catalan numbers. The nth Catalan number is given by:

$$ C_n = \frac{1}{n+1}{2n \choose n} $$

Given an integer n, compute the number of valid queue arrangements of these 2n fans.

inputFormat

The input contains a single integer n, where 1 ≤ n ≤ 30.

outputFormat

Output a single integer, the number of valid queue arrangements.

sample

1

1