Problems
Lunar Code
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 \textbf{M}×\textbf{N} containing ones and zeros. To avoid distortions during information transfer, an interesting mechanism was devised. Namely, a transferred matrix \textbf{A} must satisfy the following condition: for any \textbf{i} from \textbf{1} to \textbf{N−1}, the set \textbf{\{j | (A\[j\]\[i\]=0 И A\[j\]\[i+1\]=1)\}} must contain not more than \textbf{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".
\InputFile
The input contains integers \textbf{M}, \textbf{N} and \textbf{K}. \textbf{1} ≤ \textbf{M}, \textbf{N} ≤ \textbf{40}. \textbf{0} ≤ \textbf{K} ≤ \textbf{M}.
\OutputFile
You should output the number of different matrices satisfying the Lunar check condition.
\textbf{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