UVa 10007

Summary

The task is to find the count of rooted labeled binary trees on N vertices.

Explanation

Counts of unlabeled rooted binary trees with N vertices are exactly the famous Catalan numbers, i.e.,

${\displaystyle {\rm {count}}(N)={1 \over N+1}\cdot {2N \choose N}}$.

Once we have an unlabeled rooted binary tree with N vertices, there are exactly N! ways to add the labels. We can do this for each of the trees, thus the final answer is given by the formula

${\displaystyle {\rm {answer}}(N)=N!\cdot {1 \over N+1}\cdot {2N \choose N}={(2N)! \over (N+1)!}}$.

Implementations

As the example I/O shows, this is intended to be a BigNum problem. You only need to implement integer multiplication, as the answer can be obtained by multiplying the numbers (N+2) to 2N.

As the set of possible inputs is limited, it is possible to precompute the answers in some scripting language that supports big integers (Python, bc) and submit a program that has the answers hard-wired as string constants.

Input

1
2
10
25
0


Output

1
4
60949324800
75414671852339208296275849248768000000


Reference

1. http://mathworld.wolfram.com/CatalanNumber.html