## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Madoka and The Best University Codeforces Solution

E. Madoka and The Best University
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Madoka wants to enter to "Novosibirsk State University", but in the entrance exam she came across a very difficult task:

Given an integer $n$, it is required to calculate $\sum \mathrm{lcm}\left(c,gcd\left(a,b\right)\right)$, for all triples of positive integers $\left(a,b,c\right)$, where $a+b+c=n$.

In this problem $gcd\left(x,y\right)$ denotes the greatest common divisor of $x$ and $y$, and $\mathrm{lcm}\left(x,y\right)$ denotes the least common multiple of $x$ and $y$.

Solution Click Below:-  👉
👇👇👇👇👇

Solve this problem for Madoka and help her to enter to the best university!

Input

The first and the only line contains a single integer $n$ ($3\le n\le {10}^{5}$).

Output

Print exactly one interger — $\sum \mathrm{lcm}\left(c,gcd\left(a,b\right)\right)$. Since the answer can be very large, then output it modulo ${10}^{9}+7$.

Note

In the first example, there is only one suitable triple $\left(1,1,1\right)$. So the answer is $\mathrm{lcm}\left(1,gcd\left(1,1\right)\right)=\mathrm{lcm}\left(1,1\right)=1$.