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.


Method signature: int howMany(int N, int M, int C)
Time limit (s): 2.000
Memory limit (MB): 256


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)2003, TopCoder, Inc. All rights reserved.