樱花，樱花

题目描述

有 $k$ 棵樱花树，在第 $i$ 棵树下最多能收集到 $s_i$ 朵樱花（收集了 $0$ 朵樱花也算收集了樱花）。

你有多少种方案能够收集到恰好 $n$ 朵樱花呢？

输入格式

第一行两个正整数 $n, k$，表示要收集 $n$ 朵樱花，而前方还有 $k$ 棵樱花树。

接下来一行 $k$ 个正整数 $s_1, s_2, \cdots, s_k$，其中 $s_i$ 表示最多在第 $i$ 棵樱花树下收集到 $s_i$ 朵樱花。

输出格式

一行一个整数，表示恰好收集到 $n$ 朵樱花的方案数。

由于答案可能太大，请输出答案对 $10086001$ 取模后的值。

特殊地，如果收集不到 $n$ 朵樱花，请输出一个字符串 impossible。

样例输入 #1

3 4
1 1 1 1

样例输出 #1

5

样例输入 #2

10 9
9 6 8 7 9 6 5 4 3

样例输出 #2

68345

样例输入 #3

10 5
2 2 2 2 1

样例输出 #3

impossible

数据范围

对于 $100\%$ 的数据，$1 \leq n, k \leq 5 \times 10^3$，$0 \leq s_i \leq n$。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布