Statistics

Problem Statement for "DivFreed2"

Problem Statement

Hero likes some arrays. The arrays he likes are the arrays that have all of the following properties:
  • The length of the array is n.
  • Each element is an integer between 1 and k, inclusive.
  • Whenever A and B are two consecutive elements of the array (in this order), we have (A <= B) or (A mod B != 0).

For example, suppose n=4 and k=7. Hero will like the array {1,7,7,2} because it has the right length, all elements are in the correct range, 1 <= 7, 7 <= 7, and 7 mod 2 != 0. Hero will not like the array {4,4,4,2}.

You are given the ints n and k. Let X be the number of different arrays Hero likes. Compute and return the value (X mod 1,000,000,007).

Definition

Class:
DivFreed2
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int n, int k)
(be sure your method is public)

Constraints

  • n will be between 1 and 10, inclusive.
  • k will be between 1 and 100,000, inclusive.

Examples

  1. 2

    2

    Returns: 3

    The three arrays Hero likes are {1,1}, {1,2}, and {2,2}.

  2. 9

    1

    Returns: 1

    The only array Hero likes is {1,1,1,1,1,1,1,1,1}.

  3. 3

    3

    Returns: 15

  4. 1

    107

    Returns: 107

  5. 2

    10

    Returns: 83

  6. 2

    1234

    Returns: 1515011

  7. 3

    8

    Returns: 326

  8. 10

    100000

    Returns: 526882214

  9. 6

    76199

    Returns: 584614085

  10. 7

    81405

    Returns: 859326613

  11. 6

    99409

    Returns: 860597418

  12. 6

    90238

    Returns: 719200441

  13. 8

    6872

    Returns: 963251199

  14. 8

    13068

    Returns: 478149370

  15. 3

    99053

    Returns: 56293801

  16. 5

    80739

    Returns: 177519785

  17. 7

    55556

    Returns: 174774945

  18. 4

    99120

    Returns: 956042192

  19. 7

    94152

    Returns: 516516776

  20. 6

    81611

    Returns: 347800351

  21. 5

    54058

    Returns: 621001623

  22. 9

    88126

    Returns: 594303006

  23. 8

    48067

    Returns: 508654564

  24. 10

    91454

    Returns: 590231788

  25. 1

    1917

    Returns: 1917

  26. 8

    40215

    Returns: 304819617

  27. 10

    24847

    Returns: 757615869

  28. 4

    4221

    Returns: 792100828

  29. 9

    19389

    Returns: 422975655

  30. 6

    23959

    Returns: 412082218

  31. 10

    62418

    Returns: 560469948

  32. 10

    19249

    Returns: 665832051

  33. 7

    14909

    Returns: 946687333

  34. 10

    73275

    Returns: 380673450

  35. 3

    7325

    Returns: 163433547

  36. 4

    27250

    Returns: 19583528

  37. 1

    92650

    Returns: 92650

  38. 3

    16267

    Returns: 813344752

  39. 5

    30401

    Returns: 603311649

  40. 10

    50840

    Returns: 405729275

  41. 6

    71311

    Returns: 158423781

  42. 8

    65956

    Returns: 164283021

  43. 4

    20129

    Returns: 86395929

  44. 6

    34951

    Returns: 512466752

  45. 4

    84580

    Returns: 785890035

  46. 4

    18460

    Returns: 867620185

  47. 7

    90900

    Returns: 193664213

  48. 8

    25782

    Returns: 220023699

  49. 6

    100000

    Returns: 512016075

  50. 3

    15455

    Returns: 332299863

  51. 5

    78205

    Returns: 391488

  52. 3

    71114

    Returns: 347494848

  53. 4

    90365

    Returns: 678538167

  54. 6

    18262

    Returns: 673246457

  55. 1

    71156

    Returns: 71156

  56. 8

    84798

    Returns: 999753640

  57. 4

    73269

    Returns: 179601885

  58. 1

    14143

    Returns: 14143

  59. 2

    69739

    Returns: 862809306

  60. 10

    4822

    Returns: 285140732

  61. 3

    21968

    Returns: 770725893

  62. 1

    30392

    Returns: 30392

  63. 5

    73647

    Returns: 818310022

  64. 9

    8043

    Returns: 528848531

  65. 1

    80747

    Returns: 80747

  66. 7

    24094

    Returns: 874732270

  67. 3

    86739

    Returns: 854310152

  68. 9

    24615

    Returns: 530475099

  69. 8

    46850

    Returns: 118808788

  70. 1

    84210

    Returns: 84210

  71. 2

    3390

    Returns: 11467404

  72. 5

    79831

    Returns: 58035587

  73. 4

    32133

    Returns: 14507260

  74. 5

    51649

    Returns: 63156236

  75. 2

    95008

    Returns: 25511365

  76. 4

    62378

    Returns: 588400151

  77. 6

    67850

    Returns: 293885570

  78. 10

    33547

    Returns: 720169526

  79. 3

    57864

    Returns: 933932686

  80. 8

    96694

    Returns: 390848092

  81. 9

    35256

    Returns: 419527445

  82. 9

    69285

    Returns: 32675648

  83. 6

    96637

    Returns: 554892402

  84. 5

    83471

    Returns: 799033198

  85. 2

    29310

    Returns: 858799397

  86. 7

    85721

    Returns: 808458954

  87. 10

    32695

    Returns: 455526197

  88. 3

    50680

    Returns: 369554729

  89. 5

    4548

    Returns: 389819697

  90. 6

    80213

    Returns: 558206961

  91. 3

    90895

    Returns: 807116657

  92. 2

    18498

    Returns: 342009884

  93. 2

    4783

    Returns: 22840619

  94. 3

    49987

    Returns: 679936569

  95. 4

    31457

    Returns: 246824467

  96. 10

    12823

    Returns: 852513267

  97. 1

    70265

    Returns: 70265

  98. 2

    54011

    Returns: 916645214

  99. 10

    37395

    Returns: 130943290

  100. 6

    29049

    Returns: 350465115

  101. 3

    11479

    Returns: 318076859

  102. 3

    54588

    Returns: 74215924

  103. 3

    42364

    Returns: 824116816

  104. 1

    66114

    Returns: 66114

  105. 3

    82202

    Returns: 276289080

  106. 3

    72336

    Returns: 647608474

  107. 6

    78792

    Returns: 332232727

  108. 5

    8470

    Returns: 635337435

  109. 5

    100000

    Returns: 546009734

  110. 8

    64576

    Returns: 215917160

  111. 4

    47641

    Returns: 425912490

  112. 2

    41915

    Returns: 756456533

  113. 10

    19420

    Returns: 954313690

  114. 2

    96690

    Returns: 347927861

  115. 5

    34034

    Returns: 376962211

  116. 10

    96872

    Returns: 143356384

  117. 6

    11217

    Returns: 940451836

  118. 1

    60745

    Returns: 60745

  119. 6

    28893

    Returns: 176571474

  120. 2

    58664

    Returns: 440870353

  121. 4

    100000

    Returns: 233454866

  122. 4

    56838

    Returns: 162169410

  123. 8

    6319

    Returns: 253844403

  124. 1

    20094

    Returns: 20094

  125. 4

    25094

    Returns: 96729

  126. 1

    59056

    Returns: 59056

  127. 2

    47181

    Returns: 225578891

  128. 7

    46890

    Returns: 661853193

  129. 9

    99999

    Returns: 534287004

  130. 10

    97220

    Returns: 999707305

  131. 10

    98989

    Returns: 116690329

  132. 8

    50000

    Returns: 277491415

  133. 9

    99199

    Returns: 794476284

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: