Can anyone please help for the approach of the question. It was asked in a previous competition.

Given a n*m unshaded matrix, we need to find the no. Of ways to shade matrix such that every n*n submatrix will have exactly k no. Of shaded cells.

m will always be greater than equal to n.

Here 1 <= k <= n*n

1 <= n <= 100

1 <= m <= 10^18

Input case

n

m

k

Output

4

5

1

28

1

3

1

1

5

37

1

1015625