Given integers $n, m, k$, and an array of positive integers $v_0, v_1, \dots, v_m$ of length $m+1$.

For a non-negative integer sequence $\{a_i\}$ of length $n$ with 1-based indexing, where each element satisfies $0 \le a_i \le m$, we define its weight as $v_{a_1} \times v_{a_2} \times \dots \times v_{a_n}$.

A sequence $\{a_i\}$ is considered a valid sequence if the number of $1$s in the binary representation of the integer $S = 2^{a_1} + 2^{a_2} + \dots + 2^{a_n}$ is at most $k$.

Calculate the sum of weights of all valid sequences $\{a_i\}$, modulo $998244353$.

Input

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

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

Output

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

Examples

Input 1

5 1 1
2 1

Output 1

40

Note 1

Since $k = 1$, and knowing $n \le S \le n \times 2^m$, we have $5 \le S \le 10$. There is only one possible value for $S$: $S = 8$. This requires $a$ to contain two $0$s and three $1$s. Thus, there are $\binom{5}{2} = 10$ possible sequences. Each sequence contributes $v_0^2 v_1^3 = 4$, so the total weight sum is $10 \times 4 = 40$.

Input 2

See sequence/sequence2.in in the contestant directory.

Output 2

See sequence/sequence2.ans in the contestant directory.

Constraints

For all test cases, it is guaranteed that $1 \le k \le n \le 30$, $0 \le m \le 100$, and $1 \le v_i < 998244353$.