Binomial coefficients P93625

The binomial coefficient or choose function $\binom{n}{k}$ is the number of ways to choose $k$ objects from $n$ objects. Its formula is well known: $$\binom{n}{k} = \frac{ n! }{ k! (n-k)! } \enspace ,$$ where $n!=n\cdot (n-1)\cdots 2\cdot 1$. This formula is not very useful from a computational point of view, because we have to deal with huge numbers (the factorial numbers) to obtain much smaller results. For instance,

$$\binom{20}{10} = \frac{ 20! }{10! 10!} = \frac{2432902008176640000}{1316819440000} = 184756 \enspace .$$ Despite the fact that the final number has only 6 digits, we need to compute $20!$, which has 19 digits. This can be a problem because the type int of 32 bits cannot store numbers with more than 10 digits.

However, this is not the only way to compute $\binom{n}{k}$. For instance, binomial coefficients satisfy the following property: $$\binom{n}{k} = \left\{ \begin{array}{ll} 1 & \mbox{if $k = 0$ or $k = n$} \\ \binom{n-1}{k-1} + \binom{n-1}{k} & \mbox{if $0<k<n$} \end{array} \right.$$ This recursive formula allow us to compute binomial coefficients with no multiplications nor divisions, by using a procedure known nowadays as “Pascal’s triangle” or “Tartaglia’s triangle”, although it has historical references more than 1000 years old:

To compute more binomial coefficients, you only have to fill more rows of the triangle. Use this idea to compute the value of several binomial coefficients.

Input

Input consists of several cases, each with two natural numbers $n$ and $k$, where $0\le n\le 30$ and $0\le k\le n$.

Output

For each case, print $\binom{n}{k}$.