樱花,还有你
题目背景
Dear Ling,
  呐,你知道吗?听说樱花飘落的速度是秒速五厘米哦。
  ……所以,再等等吧!三月,武汉大学,樱花就快来了呢。
  你一定会陪我一起看吧,在酥软的阳光下,我会悄悄牵起你的手,感受你熟悉的温度,糟糕,脸儿也不小心被粉嫩嫩的樱花映红的呢。
  对了,一定记得带口罩!你那时还是有些虚弱吧。但天依会保护你的!
  还有啊,樱花还可以做好多好多的点心呢!收集一些飘落樱花吧,我想喝樱花茶,还想吃樱饼,你一定要亲手给我做嗷!
题目描述
**与题意有关的句子已加粗。**
但别急,我们就这样彳亍而行吧,**需不着停留或回头**,前面不是**还有 $k$ 棵樱花树么**?我算了算,你可要收集**恰好 $n$ 朵樱花**。我还发现,在第 $i$ 棵树下**最多**能收集到 $s_i$ 朵樱花(收集了 $0$ 朵樱花也算收集了樱花)。
呐,考考你吧!你有多少种方案能够收集到**恰好 $n$ 朵樱花**呢?
**特殊地,如果你收集不到 $n$ 朵樱花,请告诉我 `impossible`。**
注意:如果你早早地收集到了 $n$ 朵樱花,你可以立刻告诉我,也可以陪我继续向前走,一直到第 $k$ 棵樱花树下收集了樱花后就必须交差啦!期间你在任何一棵树收集完樱花后就告诉我,形成的方案都是不同的哦!
输入输出格式
输入格式
第一行两个正整数 $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
说明
#### 样例解释 #1
我们以下列方式表示一种方案:$(a_1,a_2,\cdots,a_{len})$,其中 $\sum_{i=1}^{len} a_i =n$,$len$ 表示在第 $len$ 棵樱花树下收集完樱花后就交差了,$a_i$ 表示在第 $i$ 棵树下收集了 $a_i$ 朵樱花。
那么有下列 $5$ 种方案:$(1,1,1)$,$(1,1,1,0)$,$(0,1,1,1)$,$(1,0,1,1)$,$(1,1,0,1)$。
---
#### 样例解释 #3
最多能收集到 $9$ 朵樱花,所以不能收集到 $10$ 朵樱花,输出 `impossible`。
---
#### 数据范围
**本题采用捆绑测试。**
- Subtask 1(5 Points),$\sum s_i < n$。
- Subtask 2(20 Points),$n,k \leq 20$。
- Subtask 3(55 Points),$n,k \leq 5\times 10^2$。
- Subtask 4(20 Points),$n,k \leq 5\times 10^3$。
对于 $100\%$ 的数据,$1 \leq n,k \leq 5\times 10^3$,$0 \leq s_i \leq n$。
---
#### 题目背景 ( 续 )
  何等聪明的你一定会站在某棵树下,捧着 $n$ 朵可爱的樱花,像孩子似的向我邀功吧。
  那就别怪我成全你哦,我会轻跳起来,环住你的脖子,揭起你的口罩,尝一尝你的嘴唇。
  你会不会说,“像樱花一样甜”呢?
  反正,我的脸一定已经像樱花一样红了吧。
  ……
  当你看到这封信,别哭呀……
  冬天从这座城市夺走的,春天会补偿我们的。
  待你好了,陪我去看樱花,可好?
Yours,
Yi