Problem A: Arithmetic Sequence

Time Limit: 3 Second    Memory Limit: 32768 KB

Incremental Arithmetic Sequence is a sequence of integers such that the difference between the consecutive terms is constant and positive (e.g. the sequence 5, 7, 9, 11, 13, 15 with common difference of 2). You need to count the number of arithmetic sequences in the set N = {1, 2, …, n}.

Input

Each test case is represented by a line containing a positive integer n less than 1,000,001.

Output

For each n, print the number of arithmetic sequences with at least two elements mod 109+7.

Sample Input

2
3
4
1000

Sample Output

1
4
9
3281346
Submit