CANDY2 - Chia kẹo 2 Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 3.0 giây Giới hạn bộ nhớ: 256 megabyte Cho m cái kẹo cần chia cho n đứa trẻ . Yêu cầu : Đếm số cách chia kẹo cho n đứa trẻ sao cho mỗi đứa có ít nhất là k cái kẹo . Kết quả lấy phần dư khia chia cho 987654321 . INPUT : Dòng đầu : Gồm số nguyên dương số test : T ( T < 10000) . T dòng tiếp theo . Mỗi dòng chứa ba số nguyên dương m , n , k ( m , n , k < 109 ) . OUTPUT : Kết quả bài toán . Ví dụ input 1 3 2 1 output 2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int p(int a, int b, int m) {
    int res = 1;
    while (b) {
        if (b & 1) res = ((res % m) * (a % m)) % m;
        a = ((a % m) * (a % m)) % m;
        b /= 2;
    }
    return res;
}
int s(int n, int p) {
    int res = 0;
    while (n > 0) {
        res = res + n % p;
        n = n / p;
    }
    return res;
}
int inverse(int A, int M) {
    int m0 = M;
    int y = 0;
    int x = 1;
    if (M == 1) return 0;
    while (A > 1) {
        int q = A / M;
        int t = M;
        M = A % M;
        A = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0) x = x + m0;
    return x;
}
int mod(int a, int b, int m) {
    return ((a % m) * inverse(b, m)) % m;
}
int rem(int n) {
    while (n % 3 == 0) n = n / 3;
    while (n % 17 == 0) n = n / 17;
    while (n % 379721 == 0) n = n / 379721;
    return n;
}
int choose(int n, int k, int m) {
    if (n < 0 || k < 0 || n < k) return 0;
    int a,b,c;
    a = (s(k, 3) + s(n - k, 3) - s(n, 3)) / 2;
    b = (s(k, 17) + s(n - k, 17) - s(n, 17)) / 16;
    c = (s(k, 379721) + s(n - k, 379721) - s(n, 379721)) / 379720;
    k = min(k, n - k);
    int res = 1;
    for (int i = 1; i <= k; i++) {
        int x = rem(n - k + i);
        int y = rem(i);
        res = ((res % m) * mod(x, y, m)) % m;
    }
    res = ((res % m)*p(3, a, m)) % m;
    res = ((res % m)*p(17, b, m)) % m;
    res = ((res % m)*p(379721, c, m)) % m;
    return res;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, m, n, k;
    cin >> t;
    while (t--) {
        cin >> m >> n >> k;
        if (m < n * k) cout << 0 << '\n';
        else if (m == n * k) cout << 1 << '\n';
        else cout << choose(m - n * (k - 1) - 1, n - 1, 987654321) << '\n';
    }
    return 0;
}