时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定整数 \(n, m, k\)，和一个长度为 \(m + 1\) 的正整数数组 \(v_0, v_1, ... , v_m\)。
　　对于一个长度为 \(n\)，下标从 1 开始且每个元素均不超过 \(m\) 的非负整数序列 \({a_i}\)，我们定义它的权值为 \(v_{a_1} × v_{a_2} × · · · × v_{a_n}\)。
　　当这样的序列 \({a_i}\) 满足整数 \(S = 2^{a_1} + 2^{a_2} + ... + 2^{a_n}\) 的二进制表示中 1 的个数不超过 \(k\) 时，我们认为 \({a_i}\) 是一个合法序列。
　　计算所有合法序列 \({a_i}\) 的权值和对 998244353 取模的结果。

【输入格式】

　　输入的一行是三个整数 \(n, m, k\)。
　　第二行 \(m + 1\) 个整数，分别是 \(v_0, v_1, ... , v_m\)。

【输出格式】

　　仅一行一个整数，表示所有合法序列的权值和对 998244353 取模的结果。

【输入输出样例1】

　Input

5 1 1
2 1

　Output

40

【样例1解释】

　　由于 \(k = 1\)，而且由 \(n ≤ S ≤ n × 2^m\) 知道 \(5 ≤ S ≤ 10\)，合法的 \(S\) 只有一种可能：\(S = 8\)，这要求 \(a\) 中必须有 2 个 0 和 3 个 1，于是有 \((_5^2) = 10\) 种可能的序列，每种序列的贡献都是 \(v_0^2v_1^3 = 4\)，权值和为 \(10 × 4 = 40\)。

【数据限制】

【来源】

　　Mr.he