### 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

 Class: RooksPlacement Method: countPlacements Parameters: int, int, int Returns: int Method signature: int countPlacements(int N, int M, int K) (be sure your method is public)

### 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)

 `4` `5` `2`
`Returns: 190`
 There are only two rooks and therefore all placements are valid. The number of placements is (4 * 5) * (4 * 5 - 1) / 2 = 190.
1)

 `2` `3` `3`
`Returns: 6`
 There are 6 possible placements: ```XX. X.X .XX ..X .X. X.. ..X .X. X.. XX. X.X .XX ```
2)

 `6` `7` `20`
`Returns: 0`
3)

 `23` `37` `39`
`Returns: 288688`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7658

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10711&pm=7658

Andrew_Lazarev

#### Testers:

PabloGilberto , brett1479 , Yarin , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming