题目描述

给定整数 $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$ 取模的结果。

输入样例

5 1 1
2 1

输出样例

40

提示

【样例解释】 由于 $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$。 对所有测试点保证 $1 ≤ k ≤ n ≤ 30$, $0 ≤ m ≤ 100$, 1 ≤ v_i < 998244353。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。