Home

Contest: Task: Related: TaskG TaskI

Score : $600$ points

Problem Statement

Given are positive integers $N$, $K$, and a sequence of $K$ integers $(A_1, A_2, \ldots, A_K)$.

Takahashi and Aoki will play a game with stones. Initially, there are some heaps of stones, each of which contains one or more stones. The players take turns doing the following operation, with Takahashi going first.

  • Choose a heap with one or more stones remaining. Remove any number of stones between $1$ and $X$ (inclusive) from that heap, where $X$ is the number of stones remaining.

The player who first gets unable to do the operation loses.

Now, consider the initial arrangements of stones satisfying the following.

  • $1\leq M\leq N$ holds, where $M$ is the number of heaps of stones.
  • The number of stones in each heap is one of the following: $A_1, A_2, \ldots, A_K$.

Assuming that the heaps are ordered, there are $K+K^2+\cdots +K^N$ such initial arrangements of stones. Among them, find the number, modulo $998244353$, of arrangements that lead to Takahashi's win, assuming that both players play optimally.

Constraints

  • $1 \leq N \leq 2\times 10^5$
  • $1 \leq K < 2^{16}$
  • $1 \leq A_i < 2^{16}$
  • All $A_i$ are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2 2
1 2

Sample Output 1

4

There are six possible initial arrangements of stones: $(1)$, $(2)$, $(1,1)$, $(1,2)$, $(2,1)$, and $(2,2)$.
Takahashi has a winning strategy for four of them: $(1)$, $(2)$, $(1,2)$, and $(2,1)$, and Aoki has a winning strategy for the other two. Thus, we should print $4$.

Sample Input 2

100 3
3 5 7

Sample Output 2

112184936

Be sure to find the count modulo $998244353$.

配点 : $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$

出力

答えを出力せよ。

入力例 1

2 2
1 2

出力例 1

4

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

入力例 2

100 3
3 5 7

出力例 2

112184936

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