A. New Adventures of the Wolf of Wall Street
time limit per test
6 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Jordan Belfort has been released from prison and has decided to conquer Wall Street once again! UAM, the main organization for the extraction of ancient artifacts, also eagerly awaited his return. They contacted Jordan, the world's foremost financial mind, on the same day with the following task:

All over the world, there are plenty of numismatists with a penchant for rare Incan coins. UAM has accumulated a decent number of these coins over time. Now, the organization wants to send these coins to each of its clients.

As it turns out, each client of UAM has apparently helped them with financial savings as well. For that reason, UAM also needs to send some amount of dollars to each of them. Of course, the organization wants to send as many dollars as possible, but its main goal is to deliver a fixed number of coins to each client, and to ensure that the couriers do not raise suspicion at the airport customs control.

To start with the task, Jordan has decided how the money will be transported: the ancient coins will be placed in separate square containers which, in turn, will then be neatly arranged inside plastic bags, together with stacks of dollar bills. The bags will then be vacuum-sealed, rolled into rolls and transported this way.

To avoid raising suspicion at customs, there should be no correlation between the couriers. With clothing, appearance, and voice, Belfort knows very well how to handle it, he has pulled it off more than once. But when it comes to the money being arranged differently in the bags... the ingenious magnate pondered.

He is curious about how many rolls he can prepare so that the money is arranged differently in each pair. He has hired you, experienced programmers, to write a program that will help him figure this out.

Belfort has an infinite number of plastic bags of the same size. Their dimensions are $$$N$$$ united meters in height and $$$m$$$ united meters in width. He also has an infinite number of containers measuring $$$1 \times 1$$$ united square meters.

UAM has an infinite amount of dollars, and UAM also wants each client to receive exactly $$$K$$$ coins. At the time of Belfort's release from prison, the dollar bills have dimensions of $$$1 \times 2$$$ united square meters.

You need to find out how many different ways there are to arrange the money tightly in a bag so that there are exactly $$$K$$$ containers with coins among them. The stacks of bills can only be arranged horizontally or vertically. Belfort claims that it is impossible to vacuum-seal plastic bags safely (for the money, undoubtedly) if there are empty spaces, therefore, each bag must be packed to the brim, so packings with empty spaces not filled with money are not allowed!

Since the number of people who can be Belfort's accomplices on Earth is limited, the answer must be calculated modulo $$$2^{32}$$$.

Input

The single line of input contains three space-separated integers $$$N$$$, $$$m$$$, and $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq m \leq 4$$$, $$$0 \leq K \leq 100$$$).

Output

You need to output the number of different ways to arrange the containers with coins of size $$$1 \times 1$$$ and stacks of dollar bills of size $$$1 \times 2$$$ vertically or horizontally in a bag of size $$$N \times m$$$ so that there are exactly $$$K$$$ containers with coins.

Two ways are considered different if there exists a $$$1 \times 1$$$ square that either is filled with a stack of bills horizontally in one way and vertically in the other, or this square contains a coin in one way and a stack of bills in the other.

Since the answer can be quite large, you have to calculate it modulo $$$2^{32}$$$.

Example
Input
2 3 2
Output
11
Note

Let us start by listing all possible ways to arrange the containers:

$$$$$$ \left\lvert \begin{matrix} \hline x & x & . \\ . & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & x \\ . & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & . \\ x & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & . \\ . & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & . \\ . & . & x \\ \hline \end{matrix} \right\rvert $$$$$$

$$$$$$ \left\lvert \begin{matrix} \hline . & x & x \\ . & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & x & . \\ x & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & x & . \\ . & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & x & . \\ . & . & x \\ \hline \end{matrix} \right\rvert $$$$$$

$$$$$$ \left\lvert \begin{matrix} \hline . & . & x \\ x & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & . & x \\ . & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & . & x \\ . & . & x \\ \hline \end{matrix} \right\rvert $$$$$$

$$$$$$ \left\lvert \begin{matrix} \hline . & . & . \\ x & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & . & . \\ x & . & x \\ \hline \end{matrix} \right\rvert $$$$$$

$$$$$$ \left\lvert \begin{matrix} \hline . & . & . \\ . & x & x \\ \hline \end{matrix} \right\rvert $$$$$$

Now, let us try to place the dollars in each arrangement. In the end, we get the following ways:

$$$$$$ \left\lvert \begin{matrix} \hline x & x & v \\ h & h & v \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & v & v \\ x & v & v \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & h & h \\ x & h & h \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & h & h \\ h & h & x \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & x & x \\ v & h & h \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & x & v \\ v & x & v \\ \hline \end{matrix} \right\rvert $$$$$$

$$$$$$ \left\lvert \begin{matrix} \hline h & h & x \\ x & h & h \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & v & x \\ v & v & x \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline h & h & x \\ h & h & x \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline h & h & v \\ x & x & v \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & h & h \\ v & x & x \\ \hline \end{matrix} \right\rvert $$$$$$