Migrated from Lutece 1748 有根多叉树计数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定整数$n$和集合$S$( $1 \notin S$ )，求出含有$n$个结点，且每个非叶结点$u$的儿子数量$deg(u) \in S$的有根多叉树数量。树的结点无标号，结点的孩子有顺序。

Input

输入的第一行有两个整数$n,m$.($3 \leq n \leq 10^5 , 1 \leq m \leq n - 2$)

接下来一行有$m$个整数，分别表示$S$中的元素，输入保证两两不同.($2 \leq S_i \leq n - 1$)

Output

输出一行表示答案，因为答案可能较大，所以只需输出其在$\text{mod } 10^9 +7$意义下的值即可

Samples

3

1
1
4

Resources

Prepared by xiper