费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），例如：假如a是整数，p是质数，则a,p显然互质(即两者只有一个公约数1)，那么我们可以得到费马小定理的一个特例，即当p为质数时候， a^(p-1)≡1(mod p)。(百科)

用处：a/b%mod 的时候把除法变为乘法然后取模（a*b^(mod-2)%mod），乘法用ksm。

例题：

https://www.acwing.com/problem/content/216/

#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define fi first
#define se second 
#define bg begin()
#define ed end()
#define rbg rbegin()
#define all(x) x.bg,x.ed
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define de(x) cout<<x<<"###"<<endl
using namespace std;
const long long inf=2e18;
typedef long long ll;
typedef pair<ll,ll>pii;
typedef vector<ll>vi;
const double eps=1e-10;
const int mod=1e9+7;
const int N=2e1+5;
int a[N];
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int calc(int up,int down){
    int u=1,d=1;
    for(int i=1;i<=up;i++)d=d*i%mod;
    for(int i=down;i>down-up;i--)u=(u%mod)*(i%mod)%mod;
    //cout<<u<<"@@"<<d<<endl;
    return (u%mod)*ksm(d,mod-2)%mod;
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    int ans=0;
    for(int i=0;i<1<<n;i++){
        int sign=1;
        int up=n-1,down=m+n-1;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                down-=a[j]+1;
                sign*=-1;
            }
        }
        if(down<up)continue;
        //cout<<up<<"@@"<<down<<endl;
        //cout<<":::"<<calc(up,down)<<endl;
        ans+=sign*calc(up,down);
        ans%=mod;
    }
    cout<<(ans+mod)%mod<<endl;
}        
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif 
    ios::sync_with_stdio(false);
      cin.tie(0);
    //int t;
    //cin>>t;
    //while(t--){
        solve();
    //}
    return 0;
}