#Summer240012. Problem Collect Fruit

Problem Collect Fruit

Problem Collect Fruit

时间限制: 1s

空间限制:256MB

Description

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

(不要问为什么橡木会掉那么多种水果,MC的橡树也掉苹果23333.)

Input Format

第一行包括两个整数nnmm, 表示TannicTannic想要的水果数 nn, 以及有 mm棵橡木.

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

Output Format

输出一个整数,表示存在的方案数,答案对1145149811451498取模

若不存在满足题意的方案,请输出1-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

  • 1nm1e31\leq n,m \leq 1e3

Note

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