B. K Floors Down
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ of length $$$n$$$, and an integer $$$k$$$.

Consider all sequences $$$(x_1, x_2, \ldots, x_k)$$$ of length $$$k$$$, where each element is chosen independently as one of $$$n$$$ elements from the array $$$a$$$ (it is allowed to repeat elements). There are exactly $$$n^k$$$ such sequences.

For any chosen sequence, define:

  • $$$f_1 = x_1$$$,
  • for each $$$i = 2, 3, \ldots, k$$$: $$$f_i = \left\lfloor \dfrac{f_{i-1}}{x_i} \right\rfloor$$$, where $$$\lfloor \cdot \rfloor$$$ denotes the floor function.

The contribution of the sequence is the final value $$$f_k$$$. Your task is to compute the sum of contributions over all $$$n^k$$$ sequences. As the answer can be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq k \leq 10^9$$$) — the length of the array and the number of elements in each sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the sum of contributions modulo $$$998244353$$$.

Example
Input
3
2 2
1 2
3 1
3 1 3
3 4
1 2 3
Output
4
7
15
Note

In the first test case, we have $$$a = [1, 2]$$$ and $$$k = 2$$$. The $$$4$$$ sequences and their contributions are:

  • $$$[a_1, a_1] = [1, 1]$$$, $$$f_1 = 1$$$, $$$f_2 = \lfloor \frac{1}{1} \rfloor = 1$$$. Contribution: $$$1$$$.
  • $$$[a_1, a_2] = [1, 2]$$$, $$$f_1 = 1$$$, $$$f_2 = \lfloor \frac{1}{2} \rfloor = 0$$$. Contribution: $$$0$$$.
  • $$$[a_2, a_1] = [2, 1]$$$, $$$f_1 = 2$$$, $$$f_2 = \lfloor \frac{2}{1} \rfloor = 2$$$. Contribution: $$$2$$$.
  • $$$[a_2, a_2] = [2, 2]$$$, $$$f_1 = 2$$$, $$$f_2 = \lfloor \frac{2}{2} \rfloor = 1$$$. Contribution: $$$1$$$.
The sum of contributions is $$$1 + 0 + 2 + 1 = 4$$$.