Statistics

Problem Statement for "DistinctRemainders"

Problem Statement

You are interested in a sequence of integers S = (S[1], S[2], ..., S[K]) with the following properties:

  • K >= 1.
  • For all i, S[i] is a non-negative integer.
  • S[1] + S[2] + ... + S[K] = N.
  • S[1] mod M, S[2] mod M, ..., S[K] mod M are all different.

You are given a long N and an int M. Return the number of different valid sequences S, modulo 1,000,000,007. Two sequences S1 and S2 are considered different if they either have different number of elements, or if there is an index i such that S1[i] is different from S2[i].

Definition

Class:
DistinctRemainders
Method:
howMany
Parameters:
long, int
Returns:
int
Method signature:
int howMany(long N, int M)
(be sure your method is public)

Constraints

  • N will be between 1 and 10^18, inclusive.
  • M will be between 1 and 50, inclusive.

Examples

  1. 3

    2

    Returns: 5

    The 5 sequences are: (3) (0, 3) (1, 2) (2, 1) (3, 0)

  2. 3

    3

    Returns: 9

    The 9 sequences are: (3) (1, 2) (2, 1) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0)

  3. 58

    1

    Returns: 1

    The only sequence is (58).

  4. 572

    7

    Returns: 922572833

  5. 1000000000000000000

    20

    Returns: 240297629

    Watch out for overflows.

  6. 1

    1

    Returns: 1

  7. 1000000000000000000

    50

    Returns: 46857165

  8. 14

    7

    Returns: 643

  9. 7

    14

    Returns: 57

  10. 15

    15

    Returns: 2121

  11. 97

    23

    Returns: 768934218

  12. 1

    20

    Returns: 3

  13. 1

    50

    Returns: 3

  14. 2

    7

    Returns: 3

  15. 93

    14

    Returns: 718116655

  16. 6

    2

    Returns: 1

  17. 8473

    3

    Returns: 5651

  18. 40059

    37

    Returns: 914138702

  19. 858756

    14

    Returns: 698140627

  20. 3325264

    2

    Returns: 1

  21. 99726960

    20

    Returns: 602857538

  22. 405046580

    2

    Returns: 1

  23. 6709199525

    13

    Returns: 312260183

  24. 92774141998

    29

    Returns: 555712049

  25. 912490109202

    3

    Returns: 326883271

  26. 5073951506241

    6

    Returns: 598861277

  27. 64433690240928

    2

    Returns: 1

  28. 173767058179049

    35

    Returns: 487236212

  29. 7737496696886829

    26

    Returns: 843624497

  30. 95549062400722057

    33

    Returns: 293405701

  31. 319690881584892264

    30

    Returns: 626187333

  32. 4

    1

    Returns: 1

  33. 10

    12

    Returns: 299

  34. 991

    23

    Returns: 695583054

  35. 3130

    4

    Returns: 922030094

  36. 6998

    14

    Returns: 493245411

  37. 884994

    21

    Returns: 24078637

  38. 5615879

    13

    Returns: 798441238

  39. 93750616

    13

    Returns: 313501897

  40. 667860488

    3

    Returns: 445240327

  41. 5707439769

    1

    Returns: 1

  42. 64272166814

    14

    Returns: 243544564

  43. 477986576516

    11

    Returns: 98094246

  44. 4606736991870

    9

    Returns: 111082852

  45. 60881169868247

    4

    Returns: 723892939

  46. 392598014505174

    12

    Returns: 192249185

  47. 1429671065610848

    13

    Returns: 717138391

  48. 34533278621946847

    31

    Returns: 586731273

  49. 245299575173742828

    14

    Returns: 357350463

  50. 427783988761240522

    47

    Returns: 371449307

  51. 482273829627639113

    4

    Returns: 248716576

  52. 227091392807824344

    19

    Returns: 433082854

  53. 927736909704583337

    10

    Returns: 396475076

  54. 476282457179118177

    35

    Returns: 161075241

  55. 127572008851308845

    5

    Returns: 71426118

  56. 124918559510750750

    16

    Returns: 622052085

  57. 732591068249655412

    22

    Returns: 449342301

  58. 668126003465555919

    8

    Returns: 371382139

  59. 423953064949530647

    15

    Returns: 798649911

  60. 721181777663307639

    46

    Returns: 5816363

  61. 955361208302576247

    37

    Returns: 37396509

  62. 776066125740417664

    16

    Returns: 616443748

  63. 282399450093718453

    30

    Returns: 706241491

  64. 793663430571841969

    6

    Returns: 611994722

  65. 116764009883140394

    42

    Returns: 398644261

  66. 90403892428491992

    37

    Returns: 869771677

  67. 490189236877093361

    48

    Returns: 527504284

  68. 655845410602572598

    43

    Returns: 221794262

  69. 781804787448477614

    49

    Returns: 589605840

  70. 720343730613591728

    7

    Returns: 208289671

  71. 993293851500934210

    9

    Returns: 957411041

  72. 140402649375493885

    50

    Returns: 784795354

  73. 196693153802145406

    11

    Returns: 250848519

  74. 756378842767465288

    21

    Returns: 806609037

  75. 571702284006185944

    44

    Returns: 185789492

  76. 829124358688175621

    43

    Returns: 959786252

  77. 410293588970904228

    29

    Returns: 455746555

  78. 850011684922242067

    37

    Returns: 861781979

  79. 782811923016652338

    46

    Returns: 906670156

  80. 783877770011034090

    23

    Returns: 866276678

  81. 727737286228695814

    16

    Returns: 212815630

  82. 649920229735208654

    28

    Returns: 79599807

  83. 777517989043429657

    29

    Returns: 722198808

  84. 814895441298133647

    30

    Returns: 109189308

  85. 14963006823662992

    16

    Returns: 22445463

  86. 505292692323842888

    42

    Returns: 36508528

  87. 410803061604391380

    25

    Returns: 473478163

  88. 17341098467994024

    36

    Returns: 752034595

  89. 216404853972400785

    37

    Returns: 624762120

  90. 208575354064882855

    38

    Returns: 669159206

  91. 715034367818813278

    38

    Returns: 115471281

  92. 467771077419410734

    21

    Returns: 131733081

  93. 19479558867415190

    6

    Returns: 871083309

  94. 875931307701255497

    18

    Returns: 299370617

  95. 830789743755355385

    20

    Returns: 324571030

  96. 554074811793238223

    45

    Returns: 928845747

  97. 912818363093652897

    37

    Returns: 245478616

  98. 173837593383949663

    40

    Returns: 202744994

  99. 216349954416444224

    50

    Returns: 589161980

  100. 99999999999999999

    50

    Returns: 577168021

  101. 1000000000000

    23

    Returns: 558640185

  102. 1000000000000

    30

    Returns: 859815476

  103. 1000000000000000000

    31

    Returns: 293376536

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: