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".

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

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

Below are matrices corresponding to sample 2: