可重集方案数进阶版。
根据容斥原理，先算出从无穷集 ({inftycdot a_1,infty cdot a_2,cdots }) 中取 (s) 个的方案数，也即 (inom{n+s-1}{n-1})，然后减去有一项 (a_i) 至少为 (f_i+1) 的方案数，也即 (inom{n+s-1-(f_i+1)}{n-1})，然后加上……总之就是容斥。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, inv[25];
const int mod=1e9+7;
ll m, f[25], ans;
ll C(ll x, int y){
if(x<0 || y<0 || x<y) return 0;
x %= mod;
if(y==0) return 1;
ll ans=1;
for(int i=0; i<y; i++)
ans = (ans * (x-i)) % mod;
for(int i=1; i<=y; i++)
ans = (ans * inv[i]) % mod;
return ans;
}
int ksm(int a, int b, int p){
int re=1;
while(b){
if(b&1) re = ((ll)re * a) % p;
a = ((ll)a * a) % p;
b >>= 1;
}
return re;
}
int main(){
for(int i=1; i<=20; i++)
inv[i] = ksm(i, mod-2, mod);
cin>>n>>m;
for(int i=1; i<=n; i++)
cin>>f[i];
for(int x=0; x<(1<<n); x++){
int p=0;
ll tmp=n+m;
for(int i=0; i<n; i++)
if(x&(1<<i)){
p++;
tmp -= f[i+1];
}
tmp -= p + 1;
if(p&1) ans = (ans - C(tmp, n-1)) % mod;
else ans = (ans + C(tmp, n-1)) % mod;
}
ans = (ans + mod) % mod;
cout<<ans<<endl;
return 0;
}