Nim 计数

题目描述

给定正整数 $N$,$K$,以及由 $K$ 个整数组成的序列 $(A_1, A_2, \ldots, A_K)$。

高桥君和青木君将玩一个取石子游戏。初始时有一些石子堆,每堆有一颗或多颗石子。两位玩家轮流进行以下操作,高桥君先手。

• 选择一堆剩余石子数为 $1$ 颗以上的石子堆。设该堆当前剩余 $X$ 颗石子,则从中移除 $1$ 到 $X$ 颗石子(含端点)。

最先无法进行操作的人输。

现在,考虑满足以下条件的初始石子布局。

• 设石子堆数为 $M$,满足 $1\le M\le N$。
• 每堆的石子数都是 $A_1, A_2, \ldots, A_K$ 之一。

假设各堆是有序的,则共有 $K+K^2+\cdots+K^N$ 种这样的初始布局。在这些布局中,求出双方都采取最优策略时高桥君获胜的布局数,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

2 2
1 2

4

可能的初始石子布局共有六种:$(1)$,$(2)$,$(1,1)$,$(1,2)$,$(2,1)$,$(2,2)$。

其中四种 $(1)$,$(2)$,$(1,2)$,$(2,1)$ 高桥君有必胜策略,另外两种青木君有必胜策略。因此应输出 $4$。

100 3
3 5 7

112184936

请确保对 $998244353$ 取模后输出。

数据范围

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