Statistics

Problem Statement for "TheCowDivOne"

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:
TheCowDivOne
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,000,000, inclusive.
  • K will be between 1 and 1,000, 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. 1000

    47

    Returns: 219736903

  5. 1000000000

    1000

    Returns: 666683069

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

    1000

    Returns: 0

  21. 960

    960

    Returns: 0

  22. 63390173

    309

    Returns: 76652763

  23. 354906248

    391

    Returns: 921758847

  24. 693687879

    64

    Returns: 957863722

  25. 41610290

    158

    Returns: 253930380

  26. 450967320

    884

    Returns: 32765373

  27. 677453283

    407

    Returns: 404506710

  28. 78220433

    389

    Returns: 693266974

  29. 875638899

    290

    Returns: 646894459

  30. 584068127

    240

    Returns: 484851304

  31. 889464111

    931

    Returns: 654109757

  32. 1000000000

    1

    Returns: 1

  33. 1000000000

    2

    Returns: 499999999

  34. 1000000000

    3

    Returns: 12

  35. 1000000000

    4

    Returns: 374999971

  36. 1000000000

    5

    Returns: 600000071

  37. 999999360

    960

    Returns: 10740579

  38. 999999840

    840

    Returns: 647186760

  39. 999999360

    720

    Returns: 164606389

  40. 301481159

    279

    Returns: 170386145

  41. 690424208

    510

    Returns: 435670270

  42. 196504020

    360

    Returns: 664272542

  43. 106015896

    152

    Returns: 869719808

  44. 480359630

    445

    Returns: 49716086

  45. 364122858

    798

    Returns: 967782225

  46. 515289187

    973

    Returns: 691924672

  47. 446690368

    896

    Returns: 600294384

  48. 410112630

    360

    Returns: 108988924

  49. 347763120

    10

    Returns: 677969261

  50. 171220380

    660

    Returns: 418570244

  51. 369355080

    360

    Returns: 441426964

  52. 9259740

    360

    Returns: 97658488

  53. 912128400

    720

    Returns: 831685549

  54. 313071000

    300

    Returns: 699114382

  55. 943870000

    1000

    Returns: 378465649

  56. 735134400

    1000

    Returns: 312974202

  57. 698377680

    1000

    Returns: 199366479

  58. 551350800

    1000

    Returns: 612029886

  59. 367567200

    1000

    Returns: 259163372

  60. 735134400

    840

    Returns: 543959440

  61. 999999999

    999

    Returns: 230828207

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: