题目描述

公园里有 $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

样例输入 #1

3 4
1 1 1 1

样例输出 #1

5

样例 #2

样例输入 #2

10 9
9 6 8 7 9 6 5 4 3

样例输出 #2

68345

样例 #3

样例输入 #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。

数据范围

$1 \leq n,k \leq 5\times 10^3$，$0 \leq s_i \leq n$。