В ходе оборонительной войны против марсиан лунные программисты придумали новый способ кодирования информации. Вся информация представляется в виде матрицы A размером M × N, состоящей из нулей и единиц. Верхняя левая клетка такой полоски имеет координаты (1, 1), нижняя правая — (M, N). Чтобы передавать информацию без искажений, был разработан любопытный механизм. Перед передачей информации полоска заполняется нулями и единицами таким образом, чтобы для любого i от 1 до N − 1 выполнялось следующее условие: во множестве {j | (A[j][i]=0 и A[j][i+1]=1)} не более K элементов. После приёма информации проверяется выполнение данного условия, и в случае, если для какого-то i оно не выполняется, то полученной информации доверять нельзя. Механизм стал широко распространён и получил название "контрольное условие лунатиков".
Исходные данные
3 целых числа M, N, K. 1 ≤ M, N ≤ 40. 0 ≤ K ≤ M.
Результат
Целое число — количество заполненных матриц, удовлетворяющих контрольному условию лунатиков.
Примеры
исходные данные | результат |
---|
2 1 0
| 4
|
2 2 1
| 15
|
Замечания
Матрицы, удовлетворяющие примеру 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
Автор задачи: Александр Ипатов (идея — Александр Торопов)
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006