Description

与题意有关的句子已加粗。

但别急，我们就这样彳亍而行吧，需不着停留或回头，前面不是还有 $k$ 棵樱花树么？我算了算，你可要收集恰好 $n$ 朵樱花。我还发现，在第 $i$ 棵树下最多能收集到 $s_i$ 朵樱花（收集了 $0$ 朵樱花也算收集了樱花）。

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

特殊地，如果你收集不到 $n$ 朵樱花，请告诉我 impossible。

注意：如果你早早地收集到了 $n$ 朵樱花，你可以立刻告诉我，也可以陪我继续向前走，一直到第 $k$ 棵樱花树下收集了樱花后就必须交差啦！期间你在任何一棵树收集完樱花后就告诉我，形成的方案都是不同的哦！

Input Format

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

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

Output Format

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

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

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

3 4
1 1 1 1

5

10 9
9 6 8 7 9 6 5 4 3

68345

10 5
2 2 2 2 1

impossible

Hint

样例解释 #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