A :: Arithmetic Sequence

Time Limit: 3 Seconds    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 10⁹+7.

Sample Input

2
3
4
1000

Sample Output

1
4
9
3281346

Submit

Source: 12th Iran Nationwide Internet Contest IV