Statistics

Problem Statement for "TheCowDivTwo"

Problem Statement

Farmer John had N cows numbered 0 to N-1. One day he saw K cows running away from his farm. Fox Brus computed the sum of the numbers of the escaped cows. She only told John that the sum was divisible by N.

Your task is to help John by counting the number of possible sets of escaped cows. This number may be very big, so return it modulo 1,000,000,007.

Definition

Class:
TheCowDivTwo
Method:
find
Parameters:
int, int
Returns:
int
Method signature:
int find(int N, int K)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000, inclusive.
  • K will be between 1 and 47, inclusive.
  • K will be less than or equal to N.

Examples

  1. 7

    4

    Returns: 5

    7 cows are numbered 0 to 6 and 4 of them run away. Possible sets of escaped cows are {0, 1, 2, 4}, {0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}.

  2. 1

    1

    Returns: 1

  3. 58

    4

    Returns: 7322

  4. 502

    7

    Returns: 704466492

  5. 1000

    47

    Returns: 219736903

  6. 2

    1

    Returns: 1

  7. 2

    2

    Returns: 0

  8. 3

    1

    Returns: 1

  9. 3

    2

    Returns: 1

  10. 3

    3

    Returns: 1

  11. 4

    1

    Returns: 1

  12. 4

    2

    Returns: 1

  13. 4

    3

    Returns: 1

  14. 4

    4

    Returns: 0

  15. 5

    1

    Returns: 1

  16. 5

    2

    Returns: 2

  17. 5

    3

    Returns: 2

  18. 5

    4

    Returns: 1

  19. 5

    5

    Returns: 1

  20. 47

    47

    Returns: 1

  21. 1000

    1

    Returns: 1

  22. 1000

    2

    Returns: 499

  23. 1000

    3

    Returns: 166167

  24. 1000

    4

    Returns: 41417249

  25. 1000

    5

    Returns: 250291195

  26. 1000

    46

    Returns: 78998436

  27. 1000

    45

    Returns: 581148813

  28. 1000

    44

    Returns: 862248962

  29. 1000

    43

    Returns: 347713553

  30. 1000

    42

    Returns: 814019761

  31. 1000

    41

    Returns: 346385493

  32. 1000

    40

    Returns: 580623585

  33. 173

    21

    Returns: 456891727

  34. 248

    47

    Returns: 742986228

  35. 879

    2

    Returns: 439

  36. 290

    44

    Returns: 888231391

  37. 320

    16

    Returns: 184923077

  38. 283

    20

    Returns: 769892195

  39. 433

    16

    Returns: 737181366

  40. 899

    8

    Returns: 405731964

  41. 127

    46

    Returns: 553680656

  42. 111

    15

    Returns: 94153483

  43. 423

    36

    Returns: 317290246

  44. 7

    7

    Returns: 1

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: