P7961 [NOIP2021] Sequence.

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$.

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

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

**[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} | Test Point | $n$ | $k$ | $m$ | | :--------------: | :---: | :------: | :----: | | $1 \sim 4$ | $=8$ | $\leq n$ | $=9$ | | $5 \sim 7$ | $=30$ | ^ | $=7$ | | $8 \sim 10$ | ^ | ^ | $=12$ | | $11 \sim 13$ | ^ | $=1$ | $=100$ | | $14 \sim 15$ | $=5$ | $\leq n$ | $=50$ | | $16$ | $=15$ | ^ | $=100$ | | $17 \sim 18$ | $=30$ | ^ | $=30$ | | $19 \sim 20$ | ^ | ^ | $=100$ | Translated by ChatGPT 5