暂无测试数据。

蒜头君准备 $n$ 个红包，每个红包会送给特定的人，因此有个特殊的要求：第 $i$ 个红包所含的硬币数必须严格超过 $a_i$。那么问题来了，当前蒜头君一共有 $m$ 个硬币，他一共有多少种不同的放硬币的方案？答案太大了，你只需要输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行两个整数 $m,n\ (1\le m \le 10^6,1\le n \le 1000)$，分别表示蒜头君拥有的硬币数，以及红包数。

第二行 $n$ 个数 $a_i\ (0\le a_i \le 1000)$，表示每个红包的硬币必须超过 $a_i$。

输出格式

一个整数，表示答案对 $10^9+7$ 取模后的结果。数据保证至少存在一种方案。

样例解释

合法的方案有 $(2,3,5)$、$(2,4,4)$、$(3,3,4)$。

10 3
1
2
3

3