A number $n$ is given. Your task is to count all triangular sequences and output the remainder of dividing their count by $10^9 + 7$. A sequence is called triangular if it satisfies the following conditions:

• The length of the sequence does not exceed $n$.
• Each element is an integer from the interval $[1, n]$.
• Some three elements of this sequence can be the lengths of the sides of a non-degenerate triangle*.

Example triangular sequences for $n = 100$ are $(1, 1, 1)$ and $(16, 1, 11, 25, 100)$. In the first, the sides of the non-degenerate triangle are $(1, 1, 1)$, and in the second, they are $(16, 11, 25)$.

The sequence $(16, 1, 11, 84, 100)$ is not triangular, because no three elements form the sides of a non-degenerate triangle. The sequence $(5, 5)$ is also not triangular.

* A triangle is non-degenerate if it has a positive area. Equivalently, its vertices are not collinear.

Input

The only line contains an integer $n$ ($3 \le n \le 200\,000$).

Output

Print a single integer – the remainder of dividing the number of triangular sequences by $10^9 + 7$ (that is, $1000000007$).

Examples

Input 1

3

Output 1

15

Input 2

4

Output 2

254

Note

For $n = 3$ there are $15$ triangular sequences: $(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$.

For $n = 4$ there are $254$ triangular sequences: $(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$.