You are given integers $n,m,k$ and $m+1$ positive integers $v_0,v_1,\dots ,v_m$.

For a one-based array $\{a_i\}$ containing $n$ integers between $0$ and $m$, its weight is defined as $v_{a_1}\times v_{a_2}\times \cdots \times v_{a_n}$.

Such an array $\{a_i\}$ is valid if $S=2^{a_1}+2^{a_2}+\cdots +2^{a_n}$ contains no more than $k$ ones in its binary representation.

Calculate the sum of weights of all valid arrays $\{a_i\}$. Output the sum modulo $998244353$.

Input Specification

The first line contains $3$ integers $n,m,k$.

The second line contains $m+1$ integers $v_0,v_1,\dots ,v_m$.

Output Specification

Output a single integer, the sum of weights of all valid arrays modulo $998244353$.

Sample Input

5 1 1
2 1

Sample Output

40

Sample 1 Explanation

Because $k$ is $1$ and $n\le S\le n\times 2m$ implies $5\le S\le 10$, there is only one possible $S$: $S=8$. This requires that $a$ contains two $0$s and three $1$s. Thus, we have $\left(\begin{array}{c}5\\ 2\end{array}\right)=10$ valid arrays. Each array has weight $v_0^2{v}_1^3=4$. The sum is $40$.

Additional Samples

Additional samples can be found here.

Constraints

For all test cases, $1\le k\le n\le 30$, $0\le m\le 100$, $1\le v_i<998244353$.

Test cases	$n$	$k$	$m$
$1\sim 4$	$=8$	$\le n$	$=9$
$5\sim 7$	$=30$		$=7$
$8\sim 10$			$=12$
$11\sim 13$		$=1$	$=100$
$14\sim 15$	$=5$	$\le n$	$=50$
$16$	$=15$		$=100$
$17\sim 18$	$=30$		$=30$
$19\sim 20$			$=100$