Another Game#8675
This is a simple but ancient game. You are supposed to write down the numbers 1, 2, 3, \ldots, 2n-1, 2n consecutively in clockwise order on the ground to form a circle, and then draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one other number. No two segments are allowed to intersect.
It still seems like a simple game, doesn't it? But after you have written down the numbers, can you tell me how many different ways you can connect the numbers into pairs? Life is harder, right?
The input contains an integer (1 \leq n \leq 32).
Print in a single line the number of ways to connect the numbers into pairs.
Example 1
Example 3