Light OJ 1226 / Combinatorics

/***
 created: 2022-10-31-21.14.53
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

const ll mod=1e9+7;
const ll mx=1e6+2;
ll f[1000007];
ll invf[1000007];

ll bigmod(ll a,ll c,ll m)
{
    if(!c) return 1ll;
    ll x=bigmod(a,c/2,m);
    x=(x*x)%m;
    if(c&1){
        x=(x*a)%m;
    }
    return x;
}
void fact()
{
    f[0]=1ll;
    for(ll i=1; i<=mx; i++)
    {
        f[i]=(f[i-1]*i)%mod;
    }
    invf[mx]=bigmod(f[mx],mod-2,mod);
    for(ll i=mx-1; i>=0; i--)
    {
        invf[i]=(invf[i+1]*(i+1))%mod;
    }
}

ll nCr(ll n,ll r)
{
    if(r>n) return 0ll;
    return ((f[n]*invf[n-r])%mod * invf[r])%mod;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fact();

    test
    {
        ll n,m,i,j,k,l,sum=0;

        cin>>n; ll a[n+4];

        for(i=0; i<n; i++)
        {
            cin>>a[i];
            sum+=a[i];
        }

        ll ans=1;

        for(i=n-1; i>=0; i--)
        {
            ans*=nCr(sum-1,a[i]-1);
            ans%=mod;
            sum-=a[i];
        }

        cout<<"Case "<<cs<<": "<<ans<<nl;
    }

    get_lost_idiot;
}