该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Collect Fruit

时间限制： 1s

空间限制：256MB

Description

$TannicAcid$ 正在玩 $Terraia$. 在 $Terraria$ 世界中， 砍倒每棵树需要挥砍的次数不同，并且人物砍树时每挥动一下斧子， 树就会随机掉落一个水果（苹果、柠檬、桃子等）。在这个世界中 $Tannic$操纵的人物左侧有 $m$ 棵橡木，并且他给出了每棵树需要挥砍的次数 $num[i]$ .现在 $Tannic$ 想要恰好 $n$ 个水果，且他收集到足够水果后可能会直接回出生点也可能会继续向前行进，试求 $Tannic$ 砍树的方案数

（不要问为什么橡木会掉那么多种水果，MC的橡树也掉苹果23333.）

Input Format

第一行包括两个整数$n$，$m$, 表示$Tannic$想要的水果数 $n$， 以及有 $m$棵橡木.

第二行包括 $m$ 个整数 $num[i]$ ，表示砍倒每棵橡木所需的挥砍次数

Output Format

输出一个整数，表示存在的方案数，答案对$11451498$取模

若不存在满足题意的方案，请输出$-1$

Input Example#1

```cpp

3 4

1 1 1 1

```

Output Example#1

```cpp

5

```

Input Example#2

```cpp

6 5

2 2 1 3 4

```

Output Example#2

```cpp

71

```

Data Range

• $1\leq n，m \leq 1e3$

Note

• 对于样例 $1$ , 取$(1,1,1)$ 和 $(1,1,1,0)$ 视为两种方案，即到第三棵树收集完成后直接回家与继续向前走视为不同的方案.
• 对于一棵树，不必将其砍倒，即可以不收集其所有水果.