Description

Given $n, x, y$, compute

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

.

Input Format

The first line contains the number of queries $T$. Each of the next $T$ lines contains three integers $n, x, y$.

Output Format

Output $T$ lines, each containing one integer, the answer to the corresponding query.

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

6
66
15
126
393442025

Hint

Constraints: For 30% of the testdata, $x = y$. For another 30% of the testdata, $n \le 10^9$, $x, y \le 100$. For 100% of the testdata, $T \le 100$, $1 \le n \le 10^{18}$, $0 \le x, y \le 3000$.

Source: 2012 CTT mutual testing, by gyz.

Translated by ChatGPT 5