题目描述

有 $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。

3 4
1 1 1 1

5