给定整数 $n,m,k$，和一个长度为 $m+1$ 的正整数数组 $v_0,v_1,\dots ,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,\dots ,v_m$。

输出格式

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

样例一

input

5 1 1
2 1

output

40

explanation

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

样例二

见附件下载。

数据范围

对所有测试点保证 $1\le k\le n\le 30$，$0\le m\le 100$，$1\le v_i<998244353$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$