Description：

$n$ 种糖果，每种有 $c_i$ 个，要求取 $[a,b]$ 个，问有几种方法。

$1\leqslant n\leqslant 10,1\leqslant a\leqslant b\leqslant 10^7,1\leqslant c_i\leqslant 10^6$

Solution：

首先设 $res(i)$ 表示取小于等于 $i$ 个的方案数，那么 $ans=res(b)-res(a-1)$ ，对于每一种物品生成函数为： $F_i(x)=\frac{1-x^{c_i+1}}{1-x}$ ，那么总的方案数的生成函数就是： $$ \prod_{i=1}^n\frac{1-x^{c_i+1}}{1-x} $$ 最后求的是方案书的前缀和，他的生成函数是： $$ \prod_{i=1}^n(1-x^{c^i+1})\times \frac1{(1-x)^{n+1}} $$ 前面那个最多有 $2^n$ 项不为 $0$ ，因此可以 $2^n$ 爆算，后面那个是 $1,1,1,\dots$ 的生成函数，相当于是有 $n+1$ 个物品，每个物品有无限多，装某个体积的背包的方案数，这个可以用插板法转化成组合数，但是由于模数不是质数所以没有逆元，但是 $n$ 非常小，因此我们可以计算阶乘模 $mod\times n!$ 的值，最后再手动除掉 $n!$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,a,b;

#define MAXN 13

int c[MAXN];

#define MOD 2004

int fac;

int C(int n,int m)

{

	long long res = 1,mod = 1ll * MOD * fac;

	for(int i = m + 1;i <= n;++i)res = res * i % mod;

	return res / fac;

}

int query(int d)

{

	return C(d + n,d);

}

int dfs(int cur,int v,int d,int k)

{

	if(cur == n + 1)

	{

		if(d > k)return 0;

		return 1ll * v * query(k - d) % MOD;

	}

	else

	{

		return dfs(cur + 1,v,d,k) + dfs(cur + 1,MOD - v,d + c[cur] + 1,k);

	}

}

int calc(int k)

{

	return dfs(1,1,0,k);

}

int main()

{

	scanf("%d%d%d",&n,&a,&b);

	fac = 1;

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

	cout << (calc(b) - calc(a - 1) + MOD) % MOD;

	return 0;

}