$\pi \text{+}e$ 在高中上数学课时经常睡觉，然而每次考试都能 $AK$，这让他的同桌叶子很是膜拜。

某天，老师在课上讲二项分布的题目：

(2010天津,18改)
某射手每次射击击中目标的概率p=1/3, 且各次射击的结果相互独立, 互不影响。
记4次中击中的次数为X, 求X的数学期望与期望的方差。
(答案：4/3，8/9)

老师说：“这个，二项分布的期望就是 $np$，方差就是 $np(1-p)$，不信你们自己课后回去算。”

$\pi \text{+}e$ 一听有附加题，马上打起了精神，三下五除二用了他的黑科技“母函数求导”就轻而易举的解决了这个问题。顺便帮叶子也给科普了一下。

2016年暑假的某天，$\pi \text{+}e$ 突然想起了这件事。他想了想，把原来的问题加强了一下，变成下面这个样子：

有一个多项式函数 $f(x)$，最高次幂为 $x^m$，定义变换 $Q$：

$$Q(f,n,x)=\sum _{k=0}^{n}f(k)(\genfrac{}{}{0ex}{}{n}{k})x^k(1-x{)}^{n-k}$$

现在给定函数 $f$ 和 $n,x$，求 $Q(f,n,x)mod998244353$。

然而，众所周知，高考考完是会掉很多智商的。$\pi \text{+}e$ 发现自己已经忘记掉怎么用的黑科技了；他打电话给叶子，叶子也说不记得了。

你能帮帮他吗？

出于某种原因，函数 $f$ 由点值形式给出，即给定 $a_0,a_1,\cdots ,a_m$ 共 $m+1$ 个数，$f(x)=a_x$。可以证明该函数唯一。

输入格式

第一行三个整数 $n,m,x$，意义如前所述。

第二行共 $m+1$ 个整数，表示 $a_0,a_1,\cdots ,a_m$。

输出格式

输出一行一个数表示答案，请对 $998,244,353$ 取模。

样例一

input

4 1 332748118
0 1

output

332748119

explanation

注意到 $332748118\equiv \frac{1}{3}(\mathrm{mod}998244353)$, $332748119\equiv \frac{4}{3}(\mathrm{mod}998244353)$, $f(x)=x$, 题目中所求的表达式为：

$$\sum _{k=0}^{4}k(\genfrac{}{}{0ex}{}{4}{k}){\left(\frac{1}{3}\right)}^k{\left(\frac{2}{3}\right)}^{4-k}=\frac{4}{3}$$

此即为题目开头二项分布例题计算期望的表达式。

样例二

input

4 3 12
0 1 8 27

output

46704

explanation

经计算可得 $f(x)=x^3$

样例三

见样例数据下载。

限制与约定

对于所有的测试点，保证 $1\le n\le {10}^9,1\le m\le 2\times {10}^4,0\le a_i,x<998,244,353$。

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

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

下载

样例数据下载