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