题目描述

给定 $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$ 行，每行一个整数，表示相应的询问的答案

样例 #1

样例输入 #1

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

样例输出 #1

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