P6825 「EZEC-4」求和

给定正整数 $n$ 的值，求出下面这个式子的值： $$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)^{i + j}$$ 由于结果可能很大，所以你只需要求出结果对 $p$ 取模的值。

无

无

**本题开启 O2 优化和捆绑测试。** **为了卡掉错解开大了数据范围，请注意常数因子对程序产生的影响。** ### 样例解释 #### 样例 #1 对于第一组数据：$\operatorname{ans} = \gcd(1, 1)^2 + \gcd(1, 2)^3 + \gcd(2, 1)^3 + \gcd(2, 2)^4 = 1^2 + 1^3 + 1^3 + 2^4 = 3 + 16 = 19$。所以答案为 $19 \bmod (10^9 + 7) = 19$。 ### 数据范围 | Subtask | $\sum n$ | 分值 | 时限 | | :------: | :------: | :------: | :------: | | $1$ | $1 \leq \sum n \leq 500$ | $10 \operatorname{pts}$ | $1.00 \operatorname{s}$ | | $2$ | $1 \leq \sum n \leq 5 \times 10^5$ | $40 \operatorname{pts}$ | $3.20 \operatorname{s}$ | | $3$ | 无特殊限制 | $50 \operatorname{pts}$ | $6.00 \operatorname{s}$ | 对于 $100\%$ 的数据，$1 \leq \sum n \leq 1.5 \times 10^6$，$2 \leq p \leq 2^{31} - 1$ 且 $p$ 为质数，$1 \leq T \leq 2$。