P4464 [CTT] JZPKIL

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

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

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

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