Cargo

Problem Description

There're $n$ stores selling $m$ kinds of items. Each store only sells one kind of item, the $i$-th store sells the $a_{i}$-th kind of item. You're going to buy some items. You do the following operation $k$ times: choose a store at random, and buy one item from that store. Let there are $c_{i}$ stores selling item $i$. After all the operations, you will get unsatisfied, if and only if the following condition is satisfied:

• There exists an item $i$, where you hold exact $c_{i}$ of them, and they are all from different stores. For example, if store $1$ and $3$ are selling item $1$, and after operations, you hold exactly two items $1$, and one of them is from store $1$, where the other one is from store $3$, you will get unsatisfied. You want to know the possibility of not getting unsatisfied after $k$ operations. Output it modulo $998244353$.

Input

The first line contains the number of test cases $T$($1\le T \le 100$). For each test case: The first line contains three integers: $n,m,k$($1\le m \le n \le 2\times 10^5$,$1\le k < 998244353$). The following line contains $n$ integers $a_{1},a_{2} \dots a_{n}$($1\le a_{i} \le m$). It is guaranteed that each of the $m$ kinds of items will appear at least once. There will be no more than $10$ test cases where $n \ge 10^4$.

Output

One single integer, represents the answer.

Sample Input

4
3 2 3
1 1 2
1 1 1
1
6 3 4
1 1 1 2 3 3
8 4 19908
1 1 2 2 3 3 3 4

Sample Output

221832079
0
465231165
665765722

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）