时间限制： 4.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上的西埃斯公园正在准备 5202 年的月票发行工作。

题目描述

西埃斯公园发行的月票编号为由小写字母（a-z）和井号（#）组成的字符串：

• 月票编号的字符串长度为 $n$，记作位置 $1$ 到位置 $n$；
• 月票编号中有且仅有 $m$ 个位置固定为井号；
• 其余 $n-m$ 个位置可以自由填写 $26$ 种小写字母。

为了显示月票的发行方为西西艾弗岛上的西埃斯公园，可发行的月票编号必须满足如下要求：

• ccf 和 cspark 两种子串均出现至少一次（子串为连续的若干字符）；
• 至少存在一对 ccf 和 cspark，满足 ccf 在 cspark 前面（左侧）出现。

例如，当字符串长度为 $16$、存在一个位置为 $10$ 的井号时，以下编号的月票均为可发行的：

• ccfcspark#ccfcsp
• ccfcspark#cspark
• csparkccf#cspark
• ccsparccf#cspark

当然，可发行的月票远不止上面四种。

你的任务就是帮助西埃斯公园计算：总共能够发行多少张不同的月票？两张月票不同当且仅当两张月票的编号至少有一处位置的字符不同。

答案可能很大，你只需要求出其对 $998244353$ 取模的结果即可。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n$ 和 $m$，表示月票编号的字符串长度和井号的数量。

接下来一行包含 $m$ 个正整数 $a_1,a_2,\cdots,a_m$，表示指定的井号位置。

输出格式

输出到标准输出。

输出一个整数，表示可发行月票总数对 $998244353$ 取模的结果。

12 1
11

2028

样例 1 解释

在本样例中，受井号限制 ccf 和 cspark 只能分布在前面 $10$ 个字符中，因此二者各自只能出现一次，具体有以下三种情况：

• ccf 填写在 $1\sim 3$ 的位置，cspark 填写在 $4\sim 9$ 的位置；
• ccf 填写在 $1\sim 3$ 的位置，cspark 填写在 $5\sim 10$ 的位置；
• ccf 填写在 $2\sim 4$ 的位置，cspark 填写在 $5\sim 10$ 的位置。

上述三种情况中，都有另外两个可以填写任意小写字母的空余位置。因此可发行的月票总数为 $3\times 26^2=2028$。

14 2
4 8

35151

样例 2 解释

在本样例中，cspark 只能填写在 $9\sim 14$ 的位置，此时 ccf 只要填写在 $1\sim 3$ 或者 $5\sim 7$ 任意一处即可。

将 ccf 填写在一处后，另外一处的三个位置便可以填写任意小写字母；但请注意，两处均填写 ccf 的月票会被重复计算一次。

因此可发行的月票总数为 $2\times 26^3-1=35151$。

16 1
10

474661742

子任务

对于所有数据，保证 $9\le n\le 10^9,1\le m\le \min(n,10^6),1\le a_1<a_2<\cdots < a_m\le n$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（30 分）：保证 $n\le 15$；
• 子任务 2（30 分）：保证 $n\le 10^5$；
• 子任务 3（30 分）：保证 $n\le 10^9,m\le 10^4$；
• 子任务 4（10 分）：无特殊限制。

提示

可能存在无可发行月票的情况，此时的计算结果为 $0$。但是对所有测试点皆输出 $0$ 不会得分。