Line Counting

Time limit2sMemory limit512 MB

Summary

For each n, counts the distinct lines through at least two points of the triangular lattice {(x, y): 1 <= x <= y <= n}, modulo 1000000007.

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

Problem

Bobo has a set $P$ of $\frac{n(n + 1)}{2}$ points: $\{ (x, y) : 1 \leq x \leq y \leq n, \ x, y \in \mathbb{Z} \}$ . He would like to know the number of distinct lines passing through at least two points in $P$ , taken modulo $(10^9+7)$ .

Input

The input contains zero or more test cases and ends at end-of-file.

Each test case is a single line containing an integer $n$ ( $2 \leq n \leq 2 \cdot 10^9$ ).

The number of test cases does not exceed $10^5$ , and the sum of all $n$ does not exceed $2 \cdot 10^9$ .

Output

For each test case, output an integer that is the number of distinct lines, taken modulo $(10^9+7)$ .

Examples1

Example 1
Input
```
2
3
5
```
Expected output
```
3
9
51
```