A Very Easy Math Problem

Problem Description

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$.

Input

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)$

Output

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$.

Sample Input

3 1 3
56
5
20

Sample Output

139615686
4017
11554723

Source

2020 Multi-University Training Contest 6