Description

​ 小 Y 是一名普通高中生，而小 K 则是一个没有感情的机器人。

​ 一天，小 Y 得到了一个随机数生成器，小 Y 于是找小 K 比划比划玩耍。小 Y 每次会用随机生成器随机一个长为 $n$ 的非负整数序列 $a_1,a_2,a_3,\cdots,a_n$，然后小 K 为了证明自己是机器人，会计算出：

• 这个序列所有的长为 $n$ 的整数序列 $b$，满足 $0\le b_i\le a_i$ ，$f(\sum b_i)$ 的和。

​ 当然，小 K 每次都回答正确了。

​ 小 Y 在玩了很多次这样的游戏之后，发现了随机数生成器的奥秘：随机数生成器会生成一个 $0$ 到 $M$ 的整数，生成 $i$ 的概率是 $\binom{M}{i}p^i(1-p)^{M-i}$。

​ 小 Y 随即向小 K 询问了关于 $f$ 的信息，经过一番询问，他得到了 $f(0), f(1),f(2),\cdots,f(N)$ 的值，并且从小 K 口中了解到 $f$ 是一个不超过 $N$ 次的多项式。

​ 之后小 Y 向小 K 询问上述游戏中小 K 的回答的期望是多少，然而过去了许久小 K 仍然没有给出答案。于是小 Y 来找你求助，当然他只需要你输出答案 $\bmod 998244353$ 的结果。

Input

​ 第一行四个整数 $N,n,M,p$，分别表示多项式不超过 $N$ 次，小 Y 会生成长度为 $n$ 的序列，以及关于随机数生成器的信息。

​ 第二行给出 $N+1$ 个整数表示 $f(0),f(1),f(2),\cdots,f(N)$ 的值。

Output

一行一个非负整数表示答案

Sample

input

2 2 2 499122177‬
0 1 4

output

873463819

Constraint

对于 $100 \%$ 的数据，$N\leqslant 100000, 0 < M,n,p < 998244353, 0\leqslant f(i) <998244353$

• Subtask 1 ( 5 pts)：$N \leqslant 1$

• Subtask 2 (20 pts)：$M \leqslant 100000$

• Subtask 3 (30 pts)：$N\leqslant 2000$

• Subtask 4 ( 5 pts)：$n*M\leqslant N$

• Subtask 5 (40 pts)：无特殊限制