Description

Xiao C and Xiao W plan to play a two-player combinatorial game.

Xiao C has $n$ identical stones. Xiao W will split them into $m$ ordered piles. For the $i$-th pile, the number of stones cannot exceed $a_i$, but it is allowed to be $0$.

Then Xiao C moves first, and they take turns making moves. Each move, a player may choose a non-empty pile and take away some stones from it (at least $1$). The player who cannot make a move loses.

As experienced competitive programmers, Xiao C and Xiao W already know the strategies for many games very well, so this time they want to do something different: they want to know how many ways of splitting the stones make Xiao C have a winning strategy.

Input Format

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

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

Output Format

Output one non-negative integer, the number of valid ways modulo $998244353$.

6 3
2 3 4

4

Hint

Sample Explanation

The following $4$ ways satisfy the requirement: $(0,2,4)$, $(1,1,4)$, $(2,0,4)$, $(2,2,2)$.

Source

From the 2021 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2021).

Resources such as the editorial can be found at https://github.com/yylidiw/thupc_2/tree/master.

Translated by ChatGPT 5