给n个盒子， 每个盒子里面有f[i]个小球， 然后一共可以取sum个小球。问有多少种取法， 同一个盒子里的小球相同， 不同盒子的不同。
首先我们知道， n个盒子放sum个小球的方式一共有C(sum+n-1, n-1)种， 但是这个题， 因为每个盒子里的小球有上限， 所有用刚才那种方法不行。
但是我们可以枚举。 n只有20， 一共(1<<20)-1种状态， 每种状态， 1代表取这个盒子里的小球超过了上限， 0代表没有。
一共取sum个， 如果一个盒子里面的小球超过了上限， 那么就还剩下sum-f[i]-1个，因为可以为空， 所以要多减一。
然后就用容斥就可以了。
lucas定理， C（n, k)%mod p = C(n%p, k%p)*C(n/p, k/p)%mod p, 前面那部分可以直接算， 后面那部分继续lucas递归。
C(n, k)可以用乘法逆元算。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const ll mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
ll pow(ll a, ll b) {
ll tmp = ;
while(b) {
if(b&1LL) {
tmp = tmp*a%mod;
}
a = (a*a)%mod;
b>>=1LL;
}
return tmp;
}
ll C(ll a, ll b) {
if(a<b) {
return ;
}
if(b>a-b) {
b = a-b;
}
ll s1 = , s2 = ;
for(ll i = ; i<b; i++) {
s1 = s1*(a-i)%mod;
s2 = s2*(i+)%mod;
}
return s1*pow(s2, mod-)%mod;
}
ll lucas(ll a, ll b) {
if(b == )
return ;
return C(a%mod, b%mod)*lucas(a/mod, b/mod)%mod;
}
ll a[];
int main()
{
int n, flag;
ll s, sum, ans = ;
cin>>n>>s;
for(int i = ; i<n; i++) {
scanf("%I64d", &a[i]);
}
for(int i = ; i<(<<n); i++) {
sum = s, flag = ;
for(int j = ; j<n; j++) {
if(i&(<<j)) {
flag *= -;
sum = sum-a[j]-;
}
}
if(sum<)
continue;
ll tmp = C((sum+n-)%mod, n-)%mod;
ans = (ans+flag*tmp)%mod;
}
ans = (ans+mod)%mod;
cout<<ans<<endl;
return ;
}