题目描述

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

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

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

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

输入格式

第一行，两个正整数 $n, m$（$1 \le n \le {10}^{18}$，$1 \le m \le 10$）。

第二行，$m$ 个非负整数 $a_i$（$0 \le a_i \le {10}^{18}$）。

输出格式

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

6 3
2 3 4

4

提示

【样例解释】

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

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 https://github.com/yylidiw/thupc_2/tree/master 查看。