给定整数 n, m, k ,和一个长度为 m + 1 的正整数数组 v_0, v_1, \ldots, v_m 。
对于一个长度为 n ,下标从 1 开始且每个元素均不超过 m 的非负整数序列 \{a_i\} ,我们定义它的权值为 v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n} 。
当这样的序列 \{a_i\} 满足整数 S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n} 的二进制表示中 1 的个数不超过 k 时,我们认为 \{a_i\} 是一个合法序列。
计算所有合法序列 \{a_i\} 的权值和对 998244353 取模的结果。
输入第一行是三个整数 n, m, k 。
第二行 m + 1 个整数,分别是 v_0, v_1, \ldots, v_m 。
仅一行一个整数,表示所有合法序列的权值和对 998244353 取模的结果。
5 1 1 2 1
40
【样例解释 #1】
由于 k = 1 ,而且由 n \leq S \leq n \times 2^m 知道 5 \leq S \leq 10 ,合法的 S 只有一种可能: S = 8 ,这要求 a 中必须有 2 个 0 和 3 个 1 ,于是有 \binom{5}{2} = 10 种可能的序列,每种序列的贡献都是 v_0^2 v_1^3 = 4 ,权值和为 10 \times 4 = 40 。
对所有测试点保证 1 \leq k \leq n \leq 30 , 0 \leq m \leq 100 , 1 \leq v_i < 998244353 。