H - Nim游戏计数

得分：600分

问题描述

给定正整数$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$种。在这些方案中，找出Takahashi能够获胜的方案数量，假设双方都以最优策略进行游戏，并对$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$

输出

输出结果。

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$取模。