[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 ∑lcm(𝑐,gcd(𝑎,𝑏))$\sum \mathrm{lcm}(c,gcd(a,b))$, for all triples of positive integers (𝑎,𝑏,𝑐)$(a,b,c)$, where 𝑎+𝑏+𝑐=𝑛$a+b+c=n$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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≤𝑛≤105$3\le n\le {10}^5$).

Output

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

Note

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