Yet Another Rooks Problem#3439
You have rooks and an m \times n board. The placement of rooks on the board is called correct if no rook is between two other rooks, horizontally or vertically.
Given , , and , find the number of correct placements of rooks on the board. Since this number may be quite large, find it modulo .
The input file contains , , and (1 \leq m, n \leq 50, 1 \leq k \leq m \cdot n).
Output one number — the number of correct placements of rooks on the m \times n board modulo .
Example 1