题目背景

终于解出了dm同学的难题，dm同学同意帮v神联络。可dm同学有个习惯，就是联络同学的时候喜欢分组联络，而且分组的方式也很特别，要求第i组的的人数必须大于他指定的个数ci。在dm同学联络的时候，v神在想，按照dm同学的规则一共可以有多少种方案呢？他想啊想,终于……没想出来。于是他又想到了聪明的你，你能帮v神算出按照dm同学的规则有多少种分组方案吗？

题目描述

v神的班级共有n个人，dm同学想把同学分成M组联络，要求第i组的人数必须大于给定的正整数Ci，求有多少不同的方案？（两个是相同的方案当且仅当对于任意的一队i，两个方案的第i组同学数量相等）由于结果很大，所以你只需要输出模1000000007的值。

输入格式

第一行两个整数N和M ，后面有M行，每行一个整数，表示Ci

输出格式

仅有一行，一个整数，方案数模1000000007的值。

输入输出样例

输入 #1复制

10 3123

输出 #1复制

3

说明/提示

样例解释：

方案有三种，每组的个数分别是（3,3,4），（2,4,4），（2,3,5）。

数据范围约定：

对于30%的数据，N ,M<= 10

对于60%的数据，N ,M<=1000

对于100%的数据，N ,M<= 1000000 Ci<=1000

数据保证至少有一个方案

 

Lucas定理可以直接求 C(n, m)C(n,m) modmod pp

 

#include 
      
       #include 
       
        using namespace std;#define MOD 1000000007typedef long long LL;inline int Read(){    int s=0,w=1;    char ch=getchar();    while(ch<'0'||ch>'9'){        if(ch=='-'){            w=-1;        }        ch=getchar();    }    while(ch>='0'&&ch<='9'){        s=s*10+ch-'0';        ch=getchar();    }    return s*w;}int n, m;LL Qpow(LL a, LL b, LL p) {    LL ans = 1;    for(; b; b>>=1, (a*=a) %= p)        if(b & 1) (ans *= a) %= p;    return ans;}LL c(LL n, LL m, LL p) {    if(n < m) return 0;    if(m > n - m) m = n - m;    LL s1 = 1, s2 = 1;    for(int i=0; i