Xiao C and Xiao W are planning to play a two-player game.

Xiao C has $n$ identical stones, and Xiao W intends to divide them into $m$ ordered piles, where the number of stones in the $i$-th pile cannot exceed $a_i$, but may be $0$.

Afterward, Xiao C goes first, and the two players take turns. In each turn, a player chooses a non-empty pile and removes some number of stones (at least $1$) from it. The player who cannot make a move loses.

As veterans of competitive programming, Xiao C and Xiao W are well-versed in the strategies for various games. This time, they want to play something different: they want to know how many ways to divide the stones exist such that Xiao C has a winning strategy.

Input

The first line contains two positive integers $n, m$ ($n \leq 10^{18}, m \leq 10$).

The second line contains $m$ non-negative integers $a_i$ ($a_i \leq 10^{18}$).

Output

A single non-negative integer representing the number of ways modulo $998244353$.

Examples

Input 1

6 3
2 3 4

Output 1

4

Note 1

The following 4 schemes satisfy the conditions: $(0, 2, 4)$, $(1, 1, 4)$, $(2, 0, 4)$, and $(2, 2, 2)$.