Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#21633. 【PER #2】 2048

统计

pb 大师喜欢玩 2048。

pb 大师在一个 $1\times n$ 的网格上玩 2048,初始 $n$ 个格子都是空的。

游戏会进行若干轮,每轮将发生如下事件:

  1. 如果没有空位,游戏结束。否则随机一个 $1$ 到 $m$ 的数,随机到 $i$ 的概率是 $p_i$,再等概率随机一个空位,在空位中填入 $2^{i-1}$。

  2. 将所有数顺序不变移到最左侧。例如 _ _ x _ y z 会变成 x y z _ _ _

  3. 如果没有相邻相同的数,这一轮结束。否则从左往右最后一对相同的数变成他们的和以及一个空位,并且他的得分会加上产生的和,例如 x y y z _ _ 会变成 x 2y _ z _ _,并且 pb 大师会得到 $2y$ 分,接下来回到第二步。

pb 大师想要知道:他的期望总得分是多少。

输入格式

第一行两个整数 $n,m$ 分别表示网格大小和随机数的值域。

第二行 $m$ 个数,第 $i$ 个数 $a_i$ 表示 $p_i=\frac{a_i}{\sum_{j=1}^m a_j}$。

输出格式

输出一行一个整数表示期望得分对 $998244353$ 取模后的结果,具体的,设答案的最简分数为 $\frac{a}{b}$,你需要输出 $x$ 满足 $bx\equiv a\bmod 998244353$。

样例一

input

2 2
1 1

output

2

样例二

input

10 6
19 2 6 8 1 7

output

5623384

样例三

见附件下载。

数据范围

对于 $20\%$ 的数据,$1\leq n,m\leq 5$。

对于 $60\%$ 的数据,$1\leq n,m\leq 300$。

对于 $100\%$ 的数据,$1\leq n,m\leq 2000, 1\leq a_i\leq 100$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$