Description：

有 $m$ 种物品，第 $i$ 种有 $c[i]$ 个，把他分给 $n$ 个人，每个人可以分到一些相同的，但不能有人没分到，问本质不同的方案数。

$1\le n,m,c[i] \le 1000$

Solution：

首先如果不考虑不能有人没分到，那么方案数就为 $\begin{align}\prod_{i=1}^mC_{c[i]+n-1}^{n-1}\end{align}$ ，设 $S[i]$ 表示至少有 $i$ 个人没分到的方案数，根据容斥原理有 $ans=S[0]-S[1]+S[2]+\cdots+(-1)^nS[n]$ ，求 $S[i]$ 时先选出 $i$ 个强制他为 $0$ ，剩下的部分可以分到也可以没分到，所以得 $\begin{align}S[k]=C_n^k\prod_{i=1}^mC_{c[i]+(n-k)-1}^{(n-k)-1}\end{align}$ ，最后答案就是 $\begin{align}\sum_{k=0}^n(C_n^k\times(-1)^k\times \prod_{i=1}^mC_{c[i]+(n-k)-1}^{(n-k)-1})\end{align}$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000007

int n,m;

#define MAXN 2010

int c[MAXN];

typedef long long ll;

ll C[MAXN][MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)scanf("%d",&c[i]);

	C[0][0] = 1;

	for(int i = 1;i < MAXN;++i)

	{

		C[i][0] = 1;

		for(int j = 1;j <= i;++j)

		{

			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

		}

	}

	ll ans = 0;

	for(int k = 0;k <= n;++k)

	{

		ll res = (C[n][k] * ((k & 1) ? -1 : 1) + MOD) % MOD;

		for(int i = 1;i <= m;++i)

		{

			res = res * C[c[i] + (n - k) - 1][(n - k) - 1] % MOD;

		}

		ans = (ans + res) % MOD;

	}

	cout << ans << endl;

	return 0;

}