ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1476. Лунокод

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В ходе оборонительной войны против марсиан лунные программисты придумали новый способ кодирования информации. Вся информация представляется в виде матрицы 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 ≤ KM.

Результат

Целое число — количество заполненных матриц, удовлетворяющих контрольному условию лунатиков.

Примеры

исходные данныерезультат
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