CountTables | Topcoder Archive

Problem Statement

Little Petya likes rectangular tables filled with integers a lot. He is especially fond of special tables. He calls table special if and only if the following conditions are satisfied:

The table has exactly N rows and M columns.
Each cell of the table contains an integer between 1 and C, inclusive.
For any pair of row indices r1 and r2 (r1 != r2) there exist a column index c such that the numbers at cells (r1, c) and (r2, c) are different.
For any pair of column indices c1 and c2 (c1 != c2) there exist a row index r such that the numbers at cells (r, c1) and (r, c2) are different.

You are given the ints N, M, and C. Count all special tables and return their count modulo 1,000,000,007.

Definition

Class:: CountTables
Method:: howMany
Parameters:: int, int, int
Returns:: int
Method signature:: int howMany(int N, int M, int C)
(be sure your method is public)

Constraints

N, M and C will be between 1 and 4000, inclusive.

Examples

```
2
```
```
2
```
```
2
```
```
Returns: 10
```
These are the 10 special tables in this case: 11 11 12 21 12 21 11 11 22 22 21 12 21 12 22 22 12 21 21 12
```
1
```
```
1
```
```
4000
```
```
Returns: 4000
```
```
2
```
```
3
```
```
5
```
```
Returns: 13740
```
```
4000
```
```
1
```
```
4000
```
```
Returns: 593395757
```
```
5
```
```
5
```
```
1
```
```
Returns: 0
```
```
4000
```
```
4000
```
```
4000
```
```
Returns: 237003303
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.