【题意】数据重造+题解 by hansang

给定整数 $n$，求 $\prod\limits_{i=1}^n\sum\limits_{j=1}^i\gcd(i,j) \bmod (10^9+7)$。

也就是对每个小于等于 $n$ 的 $i$ ，计算 $1$ 到 $i$ 中每个 $j$ 与 $i$ 的最大公约数，将这些最大公约数相加，然后所有和相乘的到的值就是答案。

【输入格式】

一行一个正整数 $n$（$n \leq 5 \times 10^7$）

【输出格式】

一行一个整数，表示答案。

5

1080