L. Trapped in the Big Apple
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The road trip has now stopped in New York City, and it appears Walrus has snuck away at a pit stop! As usual, Walrus is scouting for places to create shrines. This time, he has met up with Kimmy in Central Park to build a Chaewon shrine. While looking for open space in Sheep Meadow, Walrus steps on a hidden tile that collapses below him, trapping him hundreds of feet under the park.

He is met by an ancient spirit who tells Walrus the following:

"In front of you are $$$n$$$ crates, numbered from $$$1$$$ to $$$n$$$, which all need to be filled with some number of apples. For crate number $$$i$$$, you need to place $$$\operatorname{lcm}(i, n)$$$ apples into that crate. If any crate has too few or too many apples, toxic fumes will enter the room and you will meet your peril. You need not worry about gathering these apples, however. Simply input the number of apples you will need in total (modulo $$$10^9 + 7$$$) into the machine on your right, and the machine will take care of the apples (or disperse the fume)."

Help Walrus avoid his peril! Given $$$n$$$, calculate $$$\sum_{i=1}^n \operatorname{lcm}(i, n)$$$, modulo $$$10^9 + 7$$$.

Input

The only input will be $$$n$$$ ($$$1 \le n \le 10^{12}$$$) — the number of crates.

Output

Output the number of apples needed, modulo $$$10^9 + 7$$$.

Examples
Input
4
Output
24
Input
6
Output
66
Note

In the first sample, the $$$4$$$ crates will have $$$4$$$, $$$4$$$, $$$12$$$, and $$$4$$$ apples.

In the second sample, we have crates labeled from $$$1$$$ to $$$6$$$. Respectively, these will have $$$6$$$, $$$6$$$, $$$6$$$, $$$12$$$, $$$30$$$, and $$$6$$$ apples.