AT_abc212_h [ABC212H] Nim Counting

题目描述

给定两个数 $N,K$，以及一个长度为 $K$ 的整数数组 $(A_1,A_2,\cdots, A_K)$。

两个人玩 Nim 游戏。

现在通过以下方式生成一个游戏：

任意选择一个 $1\le M\le N$，$M$ 表示石子堆数。

对于每一堆，其石子数是 $A$ 中任意一个数。

对于 $\sum_{i=1}^N K^i$ 种游戏，求先手获胜的游戏数，答案对 $998244353$ 取模。

输入格式

第一行两个数 $N,K$。

第二行 $K$ 个数，第 $i$ 个数为 $A_i$。

输出格式

一行一个数，表示答案。

输入输出样例 #1

输入 #1

2 2
1 2

输出 #1

4

输入输出样例 #2

输入 #2

100 3
3 5 7

输出 #2

112184936

说明/提示

• $1\le N\le 2\times 10^5$

• $1\le A_i,K<2^{16}$。

• $A_i$ 两两不同。

样例 $1$ 解释

总共有 $6$ 种可能的游戏 $(1),(2),(1,2),(2,1),(1,1),(2,2)$。

其中先手赢的是 $(1),(2),(1,2),(2,1)$,一共 $4$ 种情况。

$\textsf{\textbf{Translated by @\color{5eb95e}nr0728}}.$