题目描述

给定 $n,x,y$,求 $\sum_{i=1}^{n}(i,n)^x[i,n]^y \ \text{mod} \ 10^9+7$，其中 $(a,b)$ 为 $\gcd$，$[a,b]$ 为 $\text{lcm}$。

输入格式

第一行，询问个数 $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 \leq 10^9$，$x,y \leq 100$。
$100\%$ 的数据，$T \leq 100$，$1 \leq n \leq 10^{18}$，$0 \leq x,y \leq 3000$。