题目描述

小 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$ 取模的结果。

样例

6 3
2 3 4

4

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