Chess
Mr. Fuad loves chess so much. He only knows king's move. Now he has K kings and a "special" chess board with size N X M. He wants to know the number of ways to put K kings so that none of them attack each other.
InputThe first line of the standard input contains the number N, M and K, 1<=N<=50, 1<=M<=10, 1<=K<=8,where N = length of the board and M = width of the board and K corresponds to the number of kings to be put on the chess board.
OutputTo the standard output write one number that is the number of ways to put K kings on the chess-board so that none of them attack each other. As this number can be very big print it with modulo 1000007.
Input 1:
2 1 1Output 1:
2Input 2:
50 10 1Output 2:
500Input 3:
3 3 3Output 3:
8Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.