Лунокод

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