JOIN
Get Time

   Problem Statement  

 Problem Statement for CountTables

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

0)
    
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
1
4000
Returns: 4000
2)
    
2
3
5
Returns: 13740
3)
    
4000
1
4000
Returns: 593395757
4)
    
5
5
1
Returns: 0
5)
    
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.

This problem was used for:
       2014 TCO Algorithm Wildcard - Division I, Level Two