PowerEquation | Topcoder Archive

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

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.