Statistics

Problem Statement for "GuessTheNumberGame"

Problem Statement

You are playing the funny game "Guess the number" with a friend. In this game, one of the players chooses a positive integer and the other has to guess it by using the clues that are revealed. The i-th clue is either "Y" or "N" indicating whether the hidden number is a multiple of i or not, respectively. For instance, if the clues so far are "YYNYY" it means that the number is a multiple of 1, 2, 4 and 5, but it is not a multiple of 3.

Note that some sequences of clues are invalid. For instance, the sequence "NYYY" is invalid because all integers are multiples of 1, and therefore the starting element cannot be an "N". Also, a sequence like "YNNY" is invalid because the answer cannot be a multiple of 4, but not a multiple of 2.

You will be given an int n. Return the number of valid sequences of n clues for this game, modulo 1000000007.

Definition

Class:
GuessTheNumberGame
Method:
possibleClues
Parameters:
int
Returns:
int
Method signature:
int possibleClues(int n)
(be sure your method is public)

Notes

  • Returning the answer modulo 1000000007 means returning the remainder of dividing the answer by 1000000007.

Constraints

  • n will be between 1 and 1000000 (10^6), inclusive.

Examples

  1. 5

    Returns: 12

    The possible clues are: YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY

  2. 16

    Returns: 240

  3. 1

    Returns: 1

  4. 1000000

    Returns: 677298706

  5. 2

    Returns: 2

  6. 3

    Returns: 4

  7. 4

    Returns: 6

  8. 6

    Returns: 12

  9. 7

    Returns: 24

  10. 8

    Returns: 32

  11. 9

    Returns: 48

  12. 10

    Returns: 48

  13. 999999

    Returns: 677298706

  14. 999998

    Returns: 677298706

  15. 999997

    Returns: 677298706

  16. 999996

    Returns: 677298706

  17. 999995

    Returns: 677298706

  18. 4

    Returns: 6

  19. 5

    Returns: 12

  20. 3

    Returns: 4

  21. 262143

    Returns: 439797190

  22. 262145

    Returns: 686452591

  23. 2049

    Returns: 259455152

  24. 2047

    Returns: 571167225

  25. 257

    Returns: 371222849

  26. 16

    Returns: 240

  27. 7

    Returns: 24

  28. 512

    Returns: 165346969

  29. 127

    Returns: 557168052

  30. 16383

    Returns: 376000874

  31. 9

    Returns: 48

  32. 10

    Returns: 48

  33. 8

    Returns: 32

  34. 19682

    Returns: 107872579

  35. 27

    Returns: 3840

  36. 19684

    Returns: 230969533

  37. 28

    Returns: 3840

  38. 59050

    Returns: 861627307

  39. 6562

    Returns: 170878868

  40. 81

    Returns: 82575360

  41. 2188

    Returns: 698159760

  42. 82

    Returns: 82575360

  43. 244

    Returns: 526938414

  44. 25

    Returns: 2880

  45. 26

    Returns: 2880

  46. 24

    Returns: 1920

  47. 15624

    Returns: 323319333

  48. 390625

    Returns: 69849809

  49. 626

    Returns: 670816995

  50. 125

    Returns: 278584026

  51. 78126

    Returns: 894717118

  52. 15625

    Returns: 877205892

  53. 124

    Returns: 708938023

  54. 3125

    Returns: 907367095

  55. 126

    Returns: 278584026

  56. 390624

    Returns: 173199831

  57. 49

    Returns: 442368

  58. 50

    Returns: 442368

  59. 48

    Returns: 294912

  60. 343

    Returns: 115115442

  61. 2401

    Returns: 245747346

  62. 16806

    Returns: 45017159

  63. 117648

    Returns: 915846756

  64. 2400

    Returns: 796597881

  65. 16807

    Returns: 654020595

  66. 823542

    Returns: 769520726

  67. 823543

    Returns: 165166539

  68. 117650

    Returns: 68487875

  69. 16808

    Returns: 654020595

  70. 997

    Returns: 376725361

  71. 998

    Returns: 376725361

  72. 996

    Returns: 688362684

  73. 994009

    Returns: 536153558

  74. 994010

    Returns: 536153558

  75. 994008

    Returns: 690769041

  76. 1009

    Returns: 753450722

  77. 1010

    Returns: 753450722

  78. 1008

    Returns: 376725361

  79. 1613

    Returns: 706533350

  80. 1614

    Returns: 706533350

  81. 1612

    Returns: 353266675

  82. 99133

    Returns: 261848332

  83. 99134

    Returns: 261848332

  84. 99132

    Returns: 130924166

  85. 77591

    Returns: 144806995

  86. 77592

    Returns: 144806995

  87. 77590

    Returns: 572403501

  88. 41221

    Returns: 421018372

  89. 41222

    Returns: 421018372

  90. 41220

    Returns: 210509186

  91. 18397

    Returns: 827768751

  92. 18398

    Returns: 827768751

  93. 18396

    Returns: 913884379

  94. 130

    Returns: 636763488

  95. 195

    Returns: 549685776

  96. 172

    Returns: 517177684

  97. 1060

    Returns: 571721834

  98. 1690

    Returns: 308804503

  99. 1551

    Returns: 73587175

  100. 106318

    Returns: 895355768

  101. 124846

    Returns: 890587993

  102. 155100

    Returns: 875286419

  103. 510510

    Returns: 119256192

  104. 99999

    Returns: 456269783

  105. 571787

    Returns: 281355041

  106. 128

    Returns: 636763488

  107. 141421

    Returns: 365627645

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: