题目描述

给定正整数 $N$，$K$，以及一个长度为 $K$ 的整数序列 $(A_1, A_2, \ldots, A_K)$。

高桥和青木将玩一个有关石头的游戏。初始时，有一些石堆，每个石堆中至少包含一个石头。玩家轮流进行以下操作，高桥先开始。

• 选择一个还剩下石头的石堆，并从该石堆中移走 $1$ 到 $X$ 个（包括 $X$）石头，其中 $X$ 是该石堆中剩余的石头数量。

第一个无法进行操作的玩家输掉游戏。

现在，考虑满足以下条件的石头初始状态。

• 满足 $1\leq M\leq N$，其中 $M$ 是石堆的数量。
• 每个石堆中的石头数量为 $A_1, A_2, \ldots, A_K$ 中的某一个。

假设石堆是有序的，总共有 $K+K^2+\cdots +K^N$ 种这样的初始状态。在这些初始状态中，找出导致高桥获胜的初始状态的数量，并对 $998244353$ 取模。

约束条件

• $1 \leq N \leq 2\times 10^5$
• $1 \leq K < 2^{16}$
• $1 \leq A_i < 2^{16}$
• 所有 $A_i$ 互不相同。
• 所有输入数值为整数。

输入

输入以以下格式从标准输入给出：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_K$

输出

输出答案。

示例输入 1

2 2
1 2

示例输出 1

4

共有六种可能的石头初始状态：$(1)$, $(2)$, $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$。
高桥在其中四种状态下有必胜策略：$(1)$, $(2)$, $(1,2)$, $(2,1)$，而青木在另外两种状态下有必胜策略。因此我们应该输出 $4$。

示例输入 2

100 3
3 5 7

示例输出 2

112184936

请确保以 $998244353$ 为模计算结果的数量。