考虑表示不考虑每个人都必须分到土特产的情况下的答案,可以先每个人每种都分一个,然后用挡板来隔来转移。即。容斥一下,显然答案。
无
x
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=1010;
const int mod=1e9+7;
int n,m,a[maxn],fac[maxn<<1],inv[maxn<<1];
ll g[maxn],f[maxn][maxn];
inline int C(int x,int y)
{
if(y>x) return 0;
if(x>=mod) x%=mod;
return 1LL*fac[x]*inv[x-y]%mod*inv[y]%mod;
}
int main()
{
freopen(FIO".in","r",stdin);
freopen(FIO".out","w",stdout);
n=read(),m=read();
for(int i=1;i<=m;i++)
a[i]=read();
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=2001;i++)
fac[i]=1LL*fac[i-1]*i%mod;
for(int i=2;i<=2001;i++)
inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=2001;i++)
inv[i]=1LL*inv[i]*inv[i-1]%mod;
for(int i=1;i<=n;i++) f[0][i]=1;
for(int j=1;j<=n;j++)
for(int i=1;i<=m;i++)
f[i][j]=1LL*f[i-1][j]*C(a[i]+j-1,j-1)%mod;
for(int i=1;i<=n;i++)
{
g[i]=f[m][i];
for(int j=1;j<i;j++)
g[i]=(g[i]-g[j]*C(i,j)%mod+mod)%mod;
}
cout << g[n] << endl;
cerr<< " Time: " << (double) clock() / CLOCKS_PER_SEC << "s It Runs So Fast!" << endl;
return 0;
}