Задачи
Лунокод
Лунокод
В ходе оборонительной войны против марсиан лунные программисты придумали новый способ кодирования информации. Вся информация представляется в виде матрицы \textbf{A} размером \textbf{M}×\textbf{N}, состоящей из нулей и единиц. Верхняя левая клетка такой полоски имеет координаты (\textbf{1}, \textbf{1}), нижняя правая --- (\textbf{M}, \textbf{N}). Чтобы передавать информацию без искажений, был разработан любопытный механизм. Перед передачей информации полоска заполняется нулями и единицами таким образом, чтобы для любого \textbf{i} от \textbf{1} до \textbf{N−1} выполнялось следующее условие: во множестве \textbf{\{j | (A\[j\]\[i\]=0 И A\[j\]\[i+1\]=1)\}} не более \textbf{K} элементов. После приёма информации проверяется выполнение данного условия, и в случае, если для какого-то \textbf{i} оно не выполняется, то полученной информации доверять нельзя. Механизм стал широко распространён и получил название "контрольное условие лунатиков".
\InputFile
\textbf{3} целых числа \textbf{M}, \textbf{N}, \textbf{K}. \textbf{1} ≤ \textbf{M}, \textbf{N} ≤ \textbf{40}. \textbf{0} ≤ \textbf{K} ≤ \textbf{M}.
\OutputFile
Целое число --- количество заполненных матриц, удовлетворяющих контрольному условию лунатиков.
\textbf{Подсказка}
Матрицы, удовлетворяющие примеру 2:
10 11 10 11 10 10 11 11 00 01 00 01 00 01 00
10 10 11 11 00 01 00 01 10 10 11 11 00 00 01