题目描述
小 C 和小 W 两个人打算玩一局双人博弈游戏。
现在小 C 手里有 n 颗相同的石子,小 W 打算把它们分为有顺序的 m 堆,其中第 i 堆石子的数量不能超过 ai,但允许为 0。
随后,由小 C 先手,两人轮流进行操作,每次可以选择一堆非空的石子并拿走其中若干个(至少 1 个),无法操作者输。
作为算法竞赛界的老司机,小 C 和小 W 早已对各种游戏的策略摸得门儿清,于是这次他们打算玩点不一样的:他们想要知道,有多少种分石子的方法能使得小 C 有必胜策略。
输入格式
第一行:2 个正整数 n,m (n≤1018,m≤10)。
第二行:m 个非负整数 ai (ai≤1018)。
输出格式
一个非负整数,表示方案数对 998244353 取模的结果。
样例数据
样例 1 输入
6 3
2 3 4
样例 1 输出
4
样例 1 解释
以下 4 种方案是符合题意的:(0,2,4)、(1,1,4)、(2,0,4)、(2,2,2)。