Given are positive integers NN, KK, and a sequence of KK integers (A1,A2,…,AK)(A1,A2,…,AK).

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 11 and XX (inclusive) from that heap, where XX 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≤M≤N1≤M≤N holds, where MM is the number of heaps of stones.
• The number of stones in each heap is one of the following: A1,A2,…,AKA1,A2,…,AK.

Assuming that the heaps are ordered, there are K+K2+⋯+KNK+K2+⋯+KN such initial arrangements of stones. Among them, find the number, modulo 998244353998244353, of arrangements that lead to Takahashi's win, assuming that both players play optimally.

Input is given from Standard Input in the following format:
$N\ K$
$A_1\ A_2\ \dots\ A_K$

Print the answer.

$1≤N≤2×10^5$
$1≤K<2{16}$
$1≤A_i<2^{16}$
All $A_i$ are distinct.
All values in input are integers.

4

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