Berland 的所有巴士票都有编号。数字由 $$$n$$$ 数字组成($$$n$$$ 是偶数)。仅 $$$k$$$ 十进制数字 $$$d_1, d_2, \dots, d_k$$$ 可用于形成票号。如果 $$$0$$$ 位于这些数字之中,则数字可能有前导零。例如,如果 $$$n = 4$$$ 并且只能使用数字 $$$0$$$ 和 $$$4$$$,则 $$$0000$$$、$$$4004$$$、$$$4440$$$ 是有效的票号,而 $$$0002$$$、$$$00$$$、$$$44443$$$ 则不是。
如果前 $$$n / 2$$$ 数字之和等于剩余 $$$n / 2$$$ 数字之和,则为幸运彩票。
计算Berland中不同幸运券的数量。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(2 \le n \le 2 \cdot 10^5, 1 \le k \le 10)$$$ — 每个票号的位数,以及可以使用的不同小数位数。 $$$n$$$ 是偶数。
第二行包含一系列成对不同的整数 $$$d_1, d_2, \dots, d_k$$$ $$$(0 \le d_i \le 9)$$$ — 票号中可以使用的数字。数字以任意顺序给出。
输出
打印幸运彩票号码的数量,以 $$$998244353$$$ 为模。
示例
输入 #1
4 2 1 8
输出 #1
6
输入 #2
20 1 6
输出 #2
1
输入 #3
10 5 6 1 4 0 3
输出 #3
569725
输入#4
1000 7 5 4 0 1 8 3 2
输出#4
460571165
注意
在第一个示例中,有 $$$6$$$ 幸运彩票号码:$$$1111$$$、$$$1818$$$、$$$1881$$$、$$$8118$$$、$$$8181$$$ 和 $$$8888$$$。
第二个示例中只有一个票号,它由 $$$20$$$ 数字 $$$6$$$ 组成。这个票号是幸运的,所以答案是$$$1$$$。