Kortit II

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vl;
typedef vector <vl> vvl;
 
const ll inf = 1e18;
const ll modd = 1e9 + 7;
 
ll pow(ll a, ll n)
{
    ll ans = 1, i = 0;
    while((1ll << i) <= n)
    {
        if((1ll << i) & n)
        {
            ans *= a;
            ans %= modd;
            //cerr << i << ": " << ans << "\n";
        }
        a *= a;
        a %= modd;
        i++;
    }
    return ans;
}
 
ll cal(ll a, ll n, const vl &mul, const vl &inv)
{
    ll ans = mul[n] * inv[n - a]  % modd * inv[a] % modd;
    //ll ans = mul[n] / mul[n - a] / mul[a];
    return ans;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    ll t, n, a, b, i, k;
    cin >> t;
    vvl ans(2005, vl(2005, 0));
    vl mul(2005), inv(2005);
    mul[0] = mul[1] = inv[0] = inv[1] = 1;
    for(i = 2; i <= 2000; i++)
    {
        mul[i]  = mul[i - 1] * i % modd;
        inv[i] = pow(mul[i], modd - 2);
    }
    //cerr << "!!!!!";
    ans[2][1] = 1;
    for(k = 3; k <= 2000; k++)
        for(i = 1; i < k; i++)
        {
            ans[k][i] = (k - 1) * ans[k - 2][i - 1] % modd + i * ans[k - 1][i] % modd + ans[k - 1][i - 1] * (k - i) % modd;
            ans[k][i] %= modd;
        }
    //cerr << "??????";
    while(t--)
    {
        cin >> n >> a >> b;
        if((a == 0) && (b == 0))
        {
            cout << mul[n] << "\n";
            continue;
        }
        if(a + b > n || a * b == 0)
            {
                cout << "0\n";
                continue;
            }
        cout << cal(n - a - b, n, mul, inv) * ans[a + b][a] % modd * mul[n] % modd << "\n";
        //cerr << cal(a, n, mul, inv) << " ";
        //cerr << mul[n] * inv[n] % modd << "\n";
        //cerr << pow(n, a) << "\n";
    }
// * mul[n] / mul[n - a - b] / mul[n - a - b + 1] * mul[a + b]
    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 4, 5

Verdict: ACCEPTED

Test 5

Group: 5

Verdict: ACCEPTED

Test 6

Group: 5

Verdict: ACCEPTED