A Very Easy Math Problem

Given you $n,x,k$ , find the value of the following formula:

$$
\sum_{a_1=1}^{n}\sum_{a_2=1}^{n}\ldots \sum_{a_x=1}^{n}\left (\prod_{j=1}^{x}a_j^k\right )f(\gcd(a_1,a_2,\ldots ,a_x))\cdot \gcd(a_1,a_2,\ldots ,a_x)
$$

$\gcd(a_1,a_2,\ldots ,a_n)$ is the greatest common divisor of $a_1,a_2,...,a_n$.

The function $f(x)$ is defined as follows:

If there exists an ingeter $k\ (k>1)$ , and $k^2$ is a divisor of $x$,
then $f(x)=0$, else $f(x)=1$.

The first line contains three integers $t,k,x\ (1\le t \le 10^4,1\le k\le 10^9,1\le x\le 10^9)$

Then $t$ test cases follow. Each test case contains an integer $n\ (1\le n\le 2\times 10^5)$

For each test case, print one integer — the value of the formula.

Because the answer may be very large, please output the answer modulo $10^9+7$.

3 1 3
56
5
20

139615686
4017
11554723

2020 Multi-University Training Contest 6