You will be given three integers N, M and K. You are to calculate the number of ways to place K rooks on a NxM chessboard in such a way that no rook is attacked by more than one other rook. A rook is attacked by another rook if they share a row or a column and there are no other rooks between them. To avoid problems with big numbers the calculation should be done modulo 1,000,001.
|-||N will be between 1 and 50, inclusive.|
|-||M will be between 1 and 50, inclusive.|
|-||K will be between 1 and 100, inclusive.|