题目描述

正の整数 $N$ , $K$ と長さ $K$ の整数列 $(A_1,\ A_2,\ \ldots,\ A_K)$ が与えられます。

高橋君と青木君が石取りゲームをすることを考えます。最初、山がいくつかあり、それぞれの山には $1$ 個以上の石があります。 高橋君から始めて $2$ 人は交互に以下の操作を繰り返します。

• 石が $1$ つ以上残っているような山を $1$ つ選ぶ。 選んだ山に $X$ 個の石があるとき、 $1$ 個以上 $X$ 個以下の任意の個数の石をその山から取り除く。

先に操作ができなくなったプレイヤーが負けとなります。

さて、ゲームを始める前の初期状態として次のようなものを考えます。

• 山の個数を $M$ としたとき、 $1\leq\ M\leq\ N$ をみたす。
• 各山にある石の個数は $A_1,\ A_2,\ \ldots,\ A_K$ のいずれかである。

山の順番を並び替えて一致するものも区別するとしたとき、これをみたす初期状態として考えられるものは $K+K^2+\cdots\ +K^N$ 通りあります。このうち、 $2$ 人が自分が勝つために最適な行動をしたとき、高橋君が勝てるような初期状態の個数を $998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

题目描述

给定两个数 $N,K$,以及一个长度为 $K$ 的整数数组 $(A_i,A_2...A_K)$。

两个人玩 Nim 游戏。

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

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

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

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

输入格式

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

输出格式

一行一个数，表示答案。

数据范围

• $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}}.$

2 2
1 2

4

100 3
3 5 7

112184936

提示

制約

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ K\ <\ 2^{16}$
• $1\ \leq\ A_i\ <\ 2^{16}$
• $A_i$ は全て相異なる。
• 入力は全て整数である。

Sample Explanation 1

最初の状態における各山の石の個数として考えられるのは $(1)$ , $(2)$ , $(1,1)$ , $(1,2)$ , $(2,1)$ , $(2,2)$ の $6$ 通りです。 これらのうち、 $(1)$ , $(2)$ , $(1,2)$ , $(2,1)$ の $4$ 通りについては高橋君に必勝法が存在し、残りの $2$ 通りについては青木君に必勝法が存在します。よって、 $4$ を出力します。

Sample Explanation 2

$998244353$ で割った余りを求めることに注意してください。