Tính Tổ Hợp

View as PDF
Submit solution
Points: 1.00
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
em anh vũ
Problem type

Nhiệm vụ của bạn là tính ~m~ tổ hợp ~C_n^k~ theo modulo ~10^9 + 7~.

Tổ hợp ~C_n^k~ có thể tính theo công thức. ~C_n^k = \frac{n!}{(n - k)!k!}~.

Input

  • Dòng đầu tiền gồm số ~m~.

  • ~m~ dòng tiếp theo. Mỗi dòng gồm 2 số ~n~, ~k~.

Output
  • Gồm ~m~ dòng. Mỗi dòng là kết quả của ~C_n^k~ theo modulo ~10^9 + 7~.
Giới hạn

  • ~1 \le m \le 10^5~

  • ~0 \le k \le n \le 10^6~

Example

Input

3
5 3
8 1
9 5

Output

10
8
126

Comments

Please read the guidelines before commenting.


  • 0
    Magaming  commented on June 29, 2026, 3:19 a.m.

    include <bits/stdc++.h>

    using namespace std;

    const int MAXN = 1e6 + 5; const long long MOD = 1e9 + 7;

    long long fact[MAXN], inv_fact[MAXN];

    long long power(long long base, long long exp, long long mod) { long long result = 1; base %= mod; while (exp > 0) { if (exp & 1) result = result * base % mod; base = base * base % mod; exp >>= 1; } return result; }

    void precompute() { fact[0] = 1; for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;

    inv_fact[MAXN-1] = power(fact[MAXN-1], MOD-2, MOD);
for (int i = MAXN-2; i >= 0; i--)
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;

    }

    long long C(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] % MOD * invfact[k] % MOD * invfact[n-k] % MOD; }

    int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);

    precompute();

int m;
cin >> m;
while (m--) {
    int n, k;
    cin >> n >> k;
    cout << C(n, k) << "\n";
}
return 0;

    }