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:
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$$$.
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$$$.
For each test case, output a single integer — the sum of contributions modulo $$$998244353$$$.
32 21 23 13 1 33 41 2 3
4715
In the first test case, we have $$$a = [1, 2]$$$ and $$$k = 2$$$. The $$$4$$$ sequences and their contributions are:
| Name |
|---|


