A. Новые приключения Волка с Уолл-Стрит
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

Джордан Белфорт вышел из тюрьмы и решил вновь завоевать Уолл-Стрит! UAM — главная организация по добыче древних артефактов — также с нетерпением ждала его возвращения, и потому в тот же день связалась с ним — перед главным умом в мире денег появилась вот такая задача:

По всему миру распространились нумизматы, падкие до редких монет из мира инков. За всё время у UAM накопилось приличное количество этих монет, и теперь UAM хочет отправить каждому своему клиенту эти монеты.

Но так как каждый клиент этой организации, оказывается, помогал ей со сбережением финансов, UAM также требуется отправить каждому из них какую-нибудь сумму долларов. Организация, конечно же, хочет отправить как можно больше долларов, но главная её цель — это доставить каждому клиенту фиксированное количество монет — и чтобы в аэропорту на таможенном контроле доставщики не вызвали подозрения.

Для начала Джордан определился, как будут перевозиться деньги: древние монеты будут класться в отдельные квадратные контейнеры, которые будут затем аккуратно разложены в пластиковые пакеты вместе с пачками долларовых купюр. Далее пакеты будут вакуумировать, сворачивать в рулоны и так перевозить.

Чтобы не вызвать подозрения на таможне, нужно, чтобы между доставщиками не было никакой корреляции. С одеждой, внешностью, голосом, Белфорт прекрасно знает, как справиться — он не раз такое проворачивал. Но вот чтобы деньги по-разному лежали в пакетах... тут наш отчаянный магнат призадумался.

Ему интересно, как много пакетов он может снарядить так, чтобы в каждых двух деньги были разложены по-разному. Он нанял вас, опытных программистов, для написания программы, которая поможет ему выяснить это.

У Белфорта есть бесконечное количество пластиковых пакетов одинакового размера. Их размеры — это $$$N$$$ united-метров в высоту и $$$m$$$ united-метров в ширину. А также у него есть бесконечное количество контейнеров размером $$$1 \times 1$$$ united-метров квадратных.

У UAM есть бесконечное количество долларов, а также UAM хочет, чтобы каждому клиенту было доставлено ровно $$$K$$$ монет. Пачка долларов на момент выхода Белфорта из тюрьмы имеют размер $$$1 \times 2$$$ united-метров квадратных.

Требуется узнать, сколько есть различных способов разложить деньги вплотную в пакете так, чтобы среди них было ровно $$$K$$$ контейнеров с монетами. Раскладывать пачки купюр можно только горизонтально или вертикально. Белфорт утверждает, что пакеты с пустотами невозможно безопасно (для денег, несомненно) вакуумировать, пакет должен быть набит битком, поэтому не допускаются способы, в которых есть пустоты, не занятые деньгами!

Так как людей, которые могут быть пособниками Белфорта, на Земле ограниченное число, требуется посчитать ответ по модулю $$$2^{32}$$$.

Входные данные

В единственной строке через пробел указаны три целых числа $$$N$$$, $$$m$$$ и $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq m \leq 4$$$, $$$0 \leq K \leq 100$$$).

Выходные данные

Вам необходимо вывести количество различных способов разложить вплотную контейнеры с монетами размера $$$1 \times 1$$$ и пачки долларов размера $$$1 \times 2$$$ вертикально или горизонтально в пакете размером $$$N \times m$$$ так, чтобы контейнеров с монетами было ровно $$$K$$$ штук.

Способы считаются разными, если существует клетка размерами $$$1 \times 1$$$, которая в одном пакете заполнена пачкой, лежащей горизонтально, а в другом вертикально — или в одном пакете эта ячейка содержит контейнер с монетой, а в другом заполнена банкнотами.

Так как ответ может быть достаточно большим, требуется посчитать его по модулю $$$2^{32}$$$.

Пример
Входные данные
2 3 2
Выходные данные
11
Примечание

Давайте для начала выпишем все возможные способы расположения контейнеров:

$$$$$$ \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 $$$$$$

Теперь попытаемся в каждом способе расположить доллары, и в итоге получаем следующие способы:

$$$$$$ \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 $$$$$$