TopCoder Statistics - Problem Statement

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:: PowerEquation
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,000, inclusive.

Examples

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
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
100

Returns: 21620
22306

Returns: 68467

The answer is 1000068474 mod 10^9+7.
1

Returns: 1
1000000

Returns: 222454881
1000000000

Returns: 926728539
987654321

Returns: 60968614
346100

Returns: 830705971
671985798

Returns: 722374399
10

Returns: 222
34484254

Returns: 658621951
16544

Returns: 550602880
60

Returns: 7816
5309

Returns: 56985433
87294

Returns: 275737825
8498

Returns: 145666004
78132

Returns: 239235276
1934

Returns: 7619194
4

Returns: 32
3350685

Returns: 372937314
59666967

Returns: 718887343
18788220

Returns: 715415041
168837348

Returns: 825073895
8853

Returns: 158054421
769

Returns: 1219753
6600

Returns: 87965524
458

Returns: 436242
880790354

Returns: 756891106
94

Returns: 19090
980

Returns: 1971964
478

Returns: 474418
1322

Returns: 3577236
184943

Returns: 512394309
42

Returns: 3912
7

Returns: 97
169508

Returns: 558010513
359208134

Returns: 188843463
42969

Returns: 705305216
922009774

Returns: 208808517
594949

Returns: 502242073
397

Returns: 328897
80

Returns: 13852
76545

Returns: 747319732
6

Returns: 72
73307611

Returns: 4298432
6

Returns: 72
79059676

Returns: 257992379
85

Returns: 15733
4848620

Returns: 624573242
9

Returns: 181
84

Returns: 15388
78931

Returns: 490607477
549619

Returns: 673315723
415087976

Returns: 377581203
952165868

Returns: 650976939
12140

Returns: 296785156
802109324

Returns: 28988158
602

Returns: 750196
18

Returns: 724
99935931

Returns: 483770710
118888

Returns: 323731532
18114

Returns: 659894048
3

Returns: 15
36

Returns: 2924
2518048

Returns: 865735801
3330

Returns: 22492262
79974

Returns: 822751924
9830

Returns: 194767178
5

Returns: 49
5

Returns: 49
2347312

Returns: 17494872
5737999

Returns: 141270100
893041873

Returns: 286507270
439928879

Returns: 788810451
982

Returns: 1979914
386350

Returns: 837598960
5264246

Returns: 558282306
3845

Returns: 29955409
138752129

Returns: 994885749
1516

Returns: 4695484
3150

Returns: 20139332
940

Returns: 1815344
5

Returns: 49
27

Returns: 1631
304020

Returns: 72191901
49578005

Returns: 965251237
308624

Returns: 717921134
16350

Returns: 537744214
72

Returns: 11320
5

Returns: 49
68546241

Returns: 745488555
9059605

Returns: 980403924
8

Returns: 136
5373

Returns: 58365577
6495

Returns: 85182505
734

Returns: 1112858
55098572

Returns: 12568410
76424

Returns: 710255375
629

Returns: 819025
354544346

Returns: 420450317
3730

Returns: 28197914
6

Returns: 72
10

Returns: 222
62

Returns: 8314
6803916

Returns: 949288870
67405

Returns: 111119730
402957740

Returns: 397431299
999999998

Returns: 259993157
12345678

Returns: 661323466

Statistics

Problem Statement for "PowerEquation"

Problem Statement

Definition

Constraints

Examples