Kortit II

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2001;
vector<vector<long long>> dp(MAXN, vector<long long>(MAXN, -1));

int fact(int val) {
    long long res = 1;
    while (val > 1) {
        res = (res * val) % MOD;
        val--;
    }
    return res;
}

long long comb(int tot, int sel) {
    if (sel > tot) return 0;
    if (sel == 0 || sel == tot) return 1;
    
    vector<long long> p(sel + 1, 0);
    p[0] = 1;
    
    for (int x = 1; x <= tot; x++) {
        for (int y = min(x, sel); y > 0; y--) {
            p[y] = (p[y] + p[y-1]) % MOD;
        }
    }
    return p[sel];
}

long long solve_rec(int down, int up) {
    if (down < 0 || up < 0) return 0;
    if (down == 0 && up == 0) return 1;
    if (down + up <= 1) return 0;
    
    if (dp[down][up] != -1) return dp[down][up];
    
    long long ans = 0;
    ans = (((long long)(down + up - 1) * solve_rec(down - 1, up - 1)) % MOD);
    ans = (ans + ((long long)down * solve_rec(down, up - 1)) % MOD) % MOD;
    ans = (ans + ((long long)up * solve_rec(down - 1, up)) % MOD) % MOD;
    
    return dp[down][up] = ans;
}

long long calc(int len, int same, int up, int down) {
    if (same + up + down != len) return 0;
    if (len <= 0 || same < 0 || up < 0 || down < 0) return 0;
    
    long long p1 = comb(len, same);
    long long p2 = solve_rec(down, up);
    
    return (p1 * p2) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> q;
    
    while (q--) {
        int n, up, down;
        cin >> n >> up >> down;
        int same = n - up - down;
        
        long long ans = (calc(n, same, up, down) * fact(n)) % MOD;
        cout << ans << "\n";
    }
    
    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: TIME LIMIT EXCEEDED