配点 : $600$ 点

問題文

正の整数 $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$ で割ったあまりを求めてください。

制約

• $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)$ の $6$ 通りです。 これらのうち、 $(1)$ , $(2)$ , $(1,2)$ , $(2,1)$ の $4$ 通りについては高橋君に必勝法が存在し、残りの $2$ 通りについては青木君に必勝法が存在します。よって、 $4$ を出力します。

100 3
3 5 7

112184936

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