给定整数 n, m, k，和一个长度为 m + 1 的正整数数组 v_0, v_1, \ldots, v_m。

对于一个长度为 n，下标从 1 开始且每个元素均不超过 m 的非负整数序列 ${ai}，我们定义它的权值为 v{a1} \times v{a2} \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 取模的结果。

【样例解释 #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。

::cute-table{tuack} | 测试点 | 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 |

NOIP