Rikka 正在编写一个规则非常简单的类 2048 游戏。

Rikka 有一个包含一行 $n$ 列格子的矩形棋盘。初始时，这 $n$ 个格子中都填满了 $0$。

游戏由若干轮组成。在每一轮中，Rikka 将按如下步骤操作：

• 在每一轮开始时，Rikka 会等概率地随机选择一个值为 $0$ 的格子。然后，她会从 $1$ 到 $m$ 中随机选择一个整数 $j$，并将 $2^{j-1}$ 放入该格子中。选择每个特定 $j$ 值的概率由 $\frac{a_j}{a_1 + a_2 + \dots + a_m}$ 给出。
• 然后，Rikka 会按下一次“主页”（Home）按钮，产生以下效果：
  • 首先，所有非零数字的格子会尽可能向左移动，同时保持相对顺序。例如，如果棋盘为 $\{0, x, y, 0, 0, z, 0, \dots\}$，它将变为 $\{x, y, z, 0, 0, 0, 0, \dots\}$。
  • 接着，Rikka 会依次检查从第 $1$ 列到第 $n-1$ 列的棋盘。如果 Rikka 发现某一列 $i$ 使得第 $i$ 列和第 $i+1$ 列具有相同的非零数字，她将计算这两个相同数字的和，将其放入第 $i$ 列，并将第 $i+1$ 列的数字重置为 $0$。同时，她会将此和加到她的得分中。
  • 最后，所有非零数字的格子将再次尽可能向左移动，同时保持相对顺序。
• 如果没有剩余的零格子，游戏结束；否则，开始新的一轮，Rikka 将继续每轮按一次“主页”按钮。

例如，如果按下“主页”按钮时棋盘包含 $\{0, 2, 0, 2, 0, 2, 1, 1, 0\}$，Rikka 获得 $6$ 分，序列变化如下： $\{0, 2, 0, 2, 0, 2, 1, 1, 0\} \to \{2, 2, 2, 1, 1, 0, 0, 0, 0\} \to \{4, 0, 2, 2, 0, 0, 0, 0, 0\} \to \{4, 2, 2, 0, 0, 0, 0, 0, 0\}$。

初始时，Rikka 的得分为 $0$。Rikka 好奇如果她按照上述规则玩到游戏结束，她期望能得到多少分。如果完全表示出来，答案可能非常大，因此你只需要输出期望值对 $998\,244\,353$ 取模的结果；具体规则见输出格式。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2000$)。 第二行包含 $m$ 个整数，其中第 $i$ 个数为 $a_i$ ($1 \le a_i \le 100$)。

输出格式

输出一行一个整数：游戏结束时的期望得分，对 $998\,244\,353$ 取模。可以证明答案可以表示为 $\frac{x}{y}$，其中 $x$ 和 $y$ 是互质的非负整数。你应该输出 $x \cdot y^{998\,244\,351} \pmod{998\,244\,353}$ 的值。

样例

样例输入 1

2 2
1 1

样例输出 1

2

样例输入 2

10 6
19 2 6 8 1 7

样例输出 2

5623384

说明

在第一个样例中，Rikka 获得 $4$ 分的概率为 $\frac{1}{4}$，获得 $2$ 分的概率为 $\frac{1}{8}$，获得 $6$ 分的概率为 $\frac{1}{8}$。此外，Rikka 获得 $0$ 分的概率为 $\frac{1}{2}$。