Problem Description

You are given integers $n, m, k$, and a positive integer array $v_0, v_1, \ldots, v_m$ of length $m + 1$.

For a non-negative integer sequence $\{a_i\}$ of length $n$ (indexed from $1$) where each element is at most $m$, we define its weight as $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$.

If such a sequence $\{a_i\}$ satisfies that, in the binary representation of the integer $S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$, the number of $1$ bits is at most $k$, then we call $\{a_i\}$ a valid sequence.

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

Input Format

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

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

Output Format

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

5 1 1
2 1

40

见附件中的 sequence/sequence2.in

见附件中的 sequence/sequence2.ans

Hint

[Sample Explanation #1]

Since $k = 1$, and from $n \leq S \leq n \times 2^m$ we know $5 \leq S \leq 10$, there is only one possible valid $S$: $S = 8$. This requires that $a$ must contain $2$ zeros and $3$ ones. Therefore, there are $\binom{5}{2} = 10$ possible sequences. Each sequence contributes $v_0^2 v_1^3 = 4$, so the sum of weights is $10 \times 4 = 40$.

[Constraints]

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

::cute-table{tuack}

Translated by ChatGPT 5