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

样例三

见附件下载。

数据范围

对于 $1$ 分的数据，$1\leq n,m\leq 5$。

对于 $3$ 分 的数据，$1\leq n,m\leq 300$。

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

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

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