P7609 [THUPC 2021] Game

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.

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 one non-negative integer, the number of valid ways modulo $998244353$.

**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](https://github.com/yylidiw/thupc_2/tree/master). Translated by ChatGPT 5