[国家集训队] 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$ 行，每行一个整数，表示相应的询问的答案

5
6 0 0
6 0 1
6 1 0
6 1 1
1000000000 50 50

6
66
15
126
393442025

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