JZPKIL

给定正整数 $n$ 和非负整数 $x,y$，计算：

$$\sum_{i=1}^{n}\gcd(i,n)^x\operatorname{lcm}(i,n)^y \pmod{10^9+7}$$

对于每组询问，输出该式对 $10^9+7$ 取模后的非负余数。

输入格式

第一行一个整数 $T$，表示询问个数。

接下来 $T$ 行，每行包含三个整数 $n,x,y$。

输出格式

输出 $T$ 行，每行一个整数，表示对应询问的答案对 $10^9+7$ 取模后的非负余数。

样例输入

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

样例输出

6
66
15
126
393442025

数据范围

• $1\le T\le 100$；
• $1\le n\le 10^{18}$；
• $0\le x,y\le 3000$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

6
66
15
126
393442025