P4464 [国家集训队] JZPKIL
题目描述
给定$ n, x, y$，求
$$\sum_{i=1}^{n}\mathrm{gcd}(i,n)^x \mathrm{lcm}(i,n)^y \bmod (10^9+7)$$
输入格式
第一行，询问个数 $T$。
下面 $T$ 行，每行三个整数 $n, x, y$。
输出格式
$T$ 行，每行一个整数，表示相应的询问的答案
说明/提示
30%的数据，$x=y$
另30%的数据，$n \le 10^9, x, y \le 100$
100%的数据，$T \le 100, 1 \le n \le 10^{18}, 0 \le x, y \le 3000$
来源：2012集训队互测，by gyz