Problem Statement  
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.  
Definition  
 
Constraints  
  N will be between 1 and 50, inclusive.  
  M will be between 1 and 50, inclusive.  
  K will be between 1 and 100, inclusive.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
