Лунокод

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

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