Problem Description

给定一个大小为 $n$ 的可重集 $A$ 和非负整数 $k,x$。

对于 $A$ 的一个非空子集 $S$，定义 $sum(S)$ 为集合 $S$ 的元素权值之和，$|S|$ 为集合 $S$ 的元素个数。

计算下式对 $998244353$ 取模的结果。

$$
\sum_{S\subseteq A,S \neq \varnothing}sum(S)^k \cdot x^{|S|}
$$

Input

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行 3 个整数 $n,k,x$；（$1 \le n \leq 100，0 \le k \leq 10000，0 \leq x < 998244353$）

第二行 $n$ 个整数 $a_1,\cdots,a_n$，表示可重集 $A$。（$0 \le a_i < 998244353$）

$1 \le T \le 100$，且最多只有 3 组数据不满足 $n\le 20$ 且 $k \le 100$。

保证 $k=0$ 时没有子集的和是 0。

Output

对于每组数据，输出一行，包含一个正整数，表示所求的答案对 $998244353$ 取模的结果。

1
3 2 2
1 2 3

516