Lunar Code

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 И 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 ≤ K ≤ M.

Output

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

Hint

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