照着蓝书（算法竞赛进阶指南）做的，做完之后发现和自己的做法在具体实现上有点出入，去翻题解发现第一篇和蓝书上的配套程序一模一样，怎么想都想不明白，于是去hack数据结果好像把题解hack掉了。 这是hack数据：

2 1000000006
1000000006 1

手玩的话很容易发现只有1000000006+0和1000000005+1两种情况满足条件，但是第一个题解输出答案是3

感觉问题出现在题解程序第30行的y==0就return 1的判断上

int C(ll y,ll x){
    if (y<0||x<0||y<x) return 0;
    y%=p;
    if (y==0 || x==0) return 1;//在这里，这里是源代码第30行
    ll ans=1;
    for (int i=0;i<x;i++){
        ans=1ll*ans*(y-i)%p;
    }
    for (int i=1;i<=x;i++){
        ans=1ll*ans*inv[i]%p;
    }
    return ans;
}

假设 $p=1000000007$ ，因为 $C_y^x$ 中 $x=n-1<20$ 所以lucas定理展开后只有两项即 $C_y^x=C_{y/p}^{x/p=0} * C_{y\%p}^{x\%p=x}$ 前一项必定为 1 不用算，后一项其实就是$C_{y\%p}^{x}$了，这里就对应着代码第29行向后的求解步骤

如果 $x>y\%p$ 那么这一项一定为0，而不应该是其他的数，不过当 $x>y\%p>0$ 的时候会在第32和33行循环过程中乘到一次0，这时候是对的。但是当 $x>y\%p=0$ 的时候会直接在第30行return 1，这里是否就错了？

所以构造一个具有$C^{x\neq 0}_{y=1000000007}$的数据，这个数据就是上面说的

2 1000000006
1000000006 1

手写出来计算式子就是$C^{1}_{10000000007}-C^{1}_{0}-C^{1}_{1000000005}+C^{1}_{-2}=1000000007-0-1000000005+0=2 \ (mod\ 1000000007)$ 按照题解程序跑出来是$C^{1}_{10000000007}-C^{1}_{0}-C^{1}_{1000000005}+C^{1}_{-2}=1-0-1000000005+0=-1000000004\equiv 3 \ (mod\ 1000000007)$

不知道是我的证明哪里错了还是真的题解有问题

附个本人代码(AC了)

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=25;
const ll mod=1e9+7;

ll n,m,a[maxn];//n个集合 选m个 

ll inv[maxn];
ll qpow(ll a,ll b){
	ll ans=1,base=a;
	while(b){
		if(b&1){
			ans*=base;
			ans%=mod;
		}
		base*=base;
		base%=mod;
		b>>=1;
	}
	return ans;
}
ll inverse(ll a){
	return qpow(a,mod-2);
}
ll C(ll n,ll m){
	if(m>n || n<0 || m<0)return 0;
//	n%=mod;
//	if(n==0 || m==0)return 1;
	ll ans=1;
	for(ll i=n-m+1;i<=n;i++)
		ans=ans*i%mod;
	return ans*inv[m]%mod;
}
ll lucas(ll n,ll m){
	if(m>n || n<0 || m<0)return 0;
	if(!m)return 1;
	return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>a[i];
	inv[0]=1;
	for(int i=1;i<=20;i++)
		inv[i]=inv[i-1]*i%mod;
	for(int i=0;i<=20;i++)
		inv[i]=inverse(inv[i]);
	
	ll ans=0;
	for(int st=0,p;st<(1<<n);st++){
		p=0;
		static ll N,M;
		N=n+m-1;
		M=n-1;
		for(int i=0;i<n;i++){
			if((st>>i)&1){
				p++;
				N-=(a[i]+1);
			}
		}
		if(p&1)ans-=lucas(N,M);
		else ans+=lucas(N,M);
		ans%=mod;
	}
	cout<<(ans+mod)%mod;
	return 0;
}