3882 - 樱花，还有你

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

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

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

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

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

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

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

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

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

样例解释 #1

我们以下列方式表示一种方案：$(a_1,a2,\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。

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

luogu