Proper Divisor Sum

Time limit2sMemory limit128 MB

Summary

Given n up to 200 million, compute the cumulative sum of proper divisor sums from 1 to n modulo 1,000,000 efficiently.

Level: Medium5 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

For natural numbers A and C, C is a divisor of A if there exists a natural number B such that A = B × C. Every natural number N always has 1 and N as divisors.

In this problem, a divisor of N other than 1 and N is called a proper divisor. For example, the proper divisors of 6 are 2 and 3, while 13 has no proper divisors.

Define SOD(n) as the sum of all proper divisors of the natural number n. Thus SOD(6) = 5 and SOD(13) = 0. Also define CSOD(n) as SOD(1) + SOD(2) + ... + SOD(n).

Given an integer n, compute CSOD(n).

Input

The first line contains an integer n.

Output

Print the remainder when CSOD(n) is divided by 1,000,000.

Constraints

1 ≤ n ≤ 200,000,000

Examples2

Example 1
Input
```
100
```
Expected output
```
3150
```
Example 2
Input
```
2
```
Expected output
```
0
```