Contest Duration: - (local time) (100 minutes) Back to Home
H - Nim Counting /

Time Limit: 2 sec / Memory Limit: 1024 MB

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


### 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.

### 問題文

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

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

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

### 制約

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

### 入力例 2

100 3
3 5 7


### 出力例 2

112184936


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