ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Lunar Code

Time limit: 1.0 second
Memory limit: 64 MB
During the defense war against Martians, lunar programmers invented a new method of information encoding. The data are represented in the form of a matrix M × N containing ones and zeros. To avoid distortions during information transfer, an interesting mechanism was devised. Namely, a transferred matrix A must satisfy the following condition: for any i from 1 to N − 1, the set {j | (A[j][i]=0 and A[j][i+1]=1)} must contain not more than K elements. If a received matrix does not satisfy this condition, then the information cannot be trusted. This mechanism became widespread and got the name "Lunar check condition".

Input

The input contains integers M, N, and K (1 ≤ M, N ≤ 40. 0 ≤ KM).

Output

You should output the number of different matrices satisfying the Lunar check condition.

Samples

inputoutput
2 1 0
4
2 2 1
15

Notes

Below are matrices corresponding to sample 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
Problem Author: Alexander Ipatov (idea of Alexander Toropov)
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
To submit the solution for this problem go to the Problem set: 1476. Lunar Code