Statistics

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

  1. 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

  2. 1

    1

    4000

    Returns: 4000

  3. 2

    3

    5

    Returns: 13740

  4. 4000

    1

    4000

    Returns: 593395757

  5. 5

    5

    1

    Returns: 0

  6. 4000

    4000

    4000

    Returns: 237003303

  7. 2000

    2000

    2000

    Returns: 363514187

  8. 2

    3999

    3811

    Returns: 743190876

  9. 3299

    2

    311

    Returns: 120372229

  10. 1

    2

    1

    Returns: 0

  11. 1

    2

    3

    Returns: 6

  12. 2

    1

    3

    Returns: 6

  13. 2

    1

    2

    Returns: 2

  14. 1

    1

    1

    Returns: 1

  15. 4000

    4000

    1

    Returns: 0

  16. 4000

    4000

    2

    Returns: 368530609

  17. 4000

    4000

    2047

    Returns: 961353424

  18. 18

    18

    10

    Returns: 163652471

  19. 4000

    3999

    10

    Returns: 568930167

  20. 3999

    4000

    10

    Returns: 568930167

  21. 71

    71

    136

    Returns: 355292700

  22. 4000

    3999

    136

    Returns: 519323612

  23. 3998

    4000

    136

    Returns: 332543639

  24. 136

    136

    71

    Returns: 600912608

  25. 4000

    3997

    71

    Returns: 3363939

  26. 3995

    3999

    71

    Returns: 924972622

  27. 71

    4000

    136

    Returns: 572287292

  28. 4000

    71

    136

    Returns: 572287292

  29. 3

    4000

    2

    Returns: 0

  30. 4000

    3

    2

    Returns: 0

  31. 1000

    4000

    373

    Returns: 855546345

  32. 4000

    1001

    235

    Returns: 39261485

  33. 2187

    7

    3

    Returns: 967101847

  34. 7

    2187

    3

    Returns: 967101847

  35. 7

    2188

    3

    Returns: 0

  36. 2188

    7

    3

    Returns: 0

  37. 2187

    2187

    3

    Returns: 17158127

  38. 2186

    2186

    3

    Returns: 962973124

  39. 2187

    2186

    3

    Returns: 600151107

  40. 2186

    2187

    3

    Returns: 600151107

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: