Statistics

Problem Statement for "PowerEquationEasy"

Problem Statement

Fox Ciel is learning about exponentiation. While doing so, she has noticed some cute identities such as 9^3 = 27^2 and 2^10 = 32^2.

You are given an int n. Fox Ciel is going to write down all identities of the form a^b = c^d where 1 <= a,b,c,d <= n.

Let X be the number of such identities. Compute and return the value (X modulo (10^9 + 7)).

Definition

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

Constraints

  • n will be between 1 and 1,000,000, inclusive.

Examples

  1. 2

    Returns: 6

    We have these solutions: 1^1=1^1 1^1=1^2 1^2=1^1 1^2=1^2 2^1=2^1 2^2=2^2

  2. 3

    Returns: 15

    Now we have: 1^1=1^1 1^1=1^2 1^1=1^3 1^2=1^1 1^2=1^2 1^2=1^3 1^3=1^1 1^3=1^2 1^3=1^3 2^1=2^1 2^2=2^2 2^3=2^3 3^1=3^1 3^2=3^2 3^3=3^3

  3. 100

    Returns: 21620

  4. 22306

    Returns: 68467

    The answer is 1000068474 mod 10^9+7.

  5. 1

    Returns: 1

  6. 1000000

    Returns: 222454881

  7. 999999

    Returns: 215452596

  8. 282

    Returns: 167560

  9. 805355

    Returns: 83866721

  10. 6

    Returns: 72

  11. 286929

    Returns: 854880985

  12. 1

    Returns: 1

  13. 1605

    Returns: 5260025

  14. 7910

    Returns: 126228056

  15. 24

    Returns: 1256

  16. 10436

    Returns: 219464340

  17. 65585

    Returns: 626184529

  18. 100

    Returns: 21620

  19. 504795

    Returns: 85580307

  20. 603

    Returns: 752645

  21. 6

    Returns: 72

  22. 38

    Returns: 3228

  23. 9069

    Returns: 165837577

  24. 2929

    Returns: 17421117

  25. 179

    Returns: 68031

  26. 149716

    Returns: 906564276

  27. 7

    Returns: 97

  28. 81315

    Returns: 256093764

  29. 5

    Returns: 49

  30. 2

    Returns: 6

  31. 35319

    Returns: 504366209

  32. 8705

    Returns: 152826741

  33. 57281

    Returns: 581227335

  34. 6

    Returns: 72

  35. 69

    Returns: 10421

  36. 5

    Returns: 49

  37. 91630

    Returns: 829881448

  38. 366856

    Returns: 449270793

  39. 27

    Returns: 1631

  40. 7557

    Returns: 115232357

  41. 1

    Returns: 1

  42. 97808

    Returns: 174232187

  43. 9

    Returns: 181

  44. 2

    Returns: 6

  45. 1

    Returns: 1

  46. 135

    Returns: 39171

  47. 1803

    Returns: 6628905

  48. 180

    Returns: 68808

  49. 457142

    Returns: 348009250

  50. 6

    Returns: 72

  51. 72879

    Returns: 649744389

  52. 894914

    Returns: 780643028

  53. 454344

    Returns: 242975589

  54. 6324

    Returns: 80770776

  55. 6047

    Returns: 73870607

  56. 184

    Returns: 71800

  57. 14036

    Returns: 396510700

  58. 9

    Returns: 181

  59. 815

    Returns: 1368501

  60. 16872

    Returns: 572631064

  61. 215

    Returns: 97421

  62. 10

    Returns: 222

  63. 59

    Returns: 7547

  64. 20165

    Returns: 817543869

  65. 95086

    Returns: 122457374

  66. 93800

    Returns: 635917273

  67. 6

    Returns: 72

  68. 99999

    Returns: 42350085

  69. 22307

    Returns: 157692

  70. 100000

    Returns: 42910896

  71. 999653

    Returns: 831271252

  72. 665784

    Returns: 211205211

  73. 999898

    Returns: 811351070

  74. 1000

    Returns: 2053552

  75. 1234

    Returns: 3119474

  76. 11

    Returns: 263

  77. 12345

    Returns: 306886969

  78. 11000

    Returns: 243769740

  79. 10000

    Returns: 201555536

  80. 4

    Returns: 32

  81. 9999

    Returns: 201495247

  82. 22367

    Returns: 5531928

  83. 101

    Returns: 22021

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: