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 100003 . 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 < 1016 ) . OUTPUT : Kết quả bài toán . Ví dụ input 1 3 2 1 output 2 (làm bằng lập trình c++ cần gấp )

#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long countWays(ll m, ll n, ll k) {
    long long result = 1;
    for (ll i = 0; i < n-1; i++)
        result = (result * (m-1)) % 100003;
    return result;
}

int main() {
    ll t;
    cin >> t;
    vector<long long> results;
    for (ll i = 0; i < t; i++) {
        ll m, n, k;
        cin >> m >> n >> k;
        long long result = countWays(m, n, k);
        results.push_back(result);
    }
        for (ll i = 0; i < results.size(); i++) {
        cout << results[i] << endl;
    }
}