For each question, print C(n, r), the number of ways to choose r things from n, modulo the prime 1,000,000,007. Use factorials and modular inverses (Fermat: x^(p-2) is the inverse of x).
Input
The first line has q (1 ≤ q ≤ 1000). Each of the next q lines has n and r (0 ≤ r ≤ n ≤ 1000).
Output
One line per question: C(n, r) mod 1,000,000,007.
Examples
Example 1 · Input
3 5 2 10 0 4 4
Expected output
10 1 1
Example 2 · Input
1 6 3
Expected output
20
Hints
Hint 1
C(n, r) = n! / (r! (n - r)!). Compute the factorials modulo p.
Hint 2
Division modulo p is multiplication by an inverse: inverse(x) = power(x, p - 2).
Hint 3
Write power with repeated squaring; precompute fact[0..1000] once.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long b) {
long long result = 1;
a %= MOD;
while (b > 0) {
if (b & 1) result = result * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return result;
}
int main() {
vector<long long> fact(1001, 1);
for (int i = 1; i <= 1000; i++) fact[i] = fact[i - 1] * i % MOD;
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int n, r;
cin >> n >> r;
long long denom = fact[r] * fact[n - r] % MOD;
cout << fact[n] * power(denom, MOD - 2) % MOD << "\n";
}
return 0;
}