QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB

# 5194. 游戏

统计

题目描述

小 C 和小 W 两个人打算玩一局双人博弈游戏。

现在小 C 手里有 $n$ 颗相同的石子,小 W 打算把它们分为有顺序的 $m$ 堆,其中第 $i$ 堆石子的数量不能超过 $a_i$,但允许为 $0$。

随后,由小 C 先手,两人轮流进行操作,每次可以选择一堆非空的石子并拿走其中若干个(至少 $1$ 个),无法操作者输。

作为算法竞赛界的老司机,小 C 和小 W 早已对各种游戏的策略摸得门儿清,于是这次他们打算玩点不一样的:他们想要知道,有多少种分石子的方法能使得小 C 有必胜策略。

输入格式

第一行:$2$ 个正整数 $n,m\ (n\leq 10^{18},m \leq 10)$。

第二行:$m$ 个非负整数 $a_i\ (a_i \leq 10^{18})$。

输出格式

一个非负整数,表示方案数对 $998244353$ 取模的结果。

样例数据

样例 1 输入

6 3
2 3 4

样例 1 输出

4

样例 1 解释

以下 $4$ 种方案是符合题意的:$(0,2,4)$、$(1,1,4)$、$(2,0,4)$、$(2,2,2)$。