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 ≤ K ≤ M).
Output
You should output the number of different matrices satisfying the Lunar check condition.
Samples
input | output |
---|
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