Practice › Basics
nCr Modulo a Large Prime
Medium · Basics · Asked at Amazon, Microsoft, Codenation, DE Shaw
Answer q queries. For each query n r, print the binomial coefficient C(n, r) modulo 1,000,000,007. If r > n, the answer is 0.
Input
First line: q. Next q lines: n r.
Output
q lines, one answer per query.
Constraints
- 1 ≤ q ≤ 10^5
- 0 ≤ n, r ≤ 10^6
Precompute factorials once. Division under a prime modulus = multiplying by the modular inverse (Fermat: a^(p-2)).
Example 1
Input
3 5 2 10 0 3 5
Output
10 1 0
Example 2
Input
2 1000000 500000 20 10
Output
996692777 184756
Hints
- C(n, r) = n! / (r! · (n−r)!). Precompute all factorials up to 10^6 once.
- You cannot divide under a modulus — multiply by the modular inverse instead. For a prime p, inverse(a) = a^(p−2) mod p (fast exponentiation).
Approach
Precompute fact[i] and the inverse factorials inv[i] for all i ≤ 10^6. Compute inv[N] = fact[N]^(p−2) once with fast power, then go down: inv[i-1] = inv[i] · i. Each query is then fact[n] · inv[r] · inv[n−r] in O(1), or 0 when r > n. Keep every product in 64-bit and reduce modulo after each multiplication.
Complexity: O(N + q) time · O(N) space, N = 10^6
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
const int N = 1000000;
long long power(long long b, long long e) {
long long res = 1;
b %= MOD;
while (e > 0) {
if (e & 1) res = res * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<long long> fact(N + 1), inv(N + 1);
fact[0] = 1;
for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2);
for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
int q;
cin >> q;
while (q--) {
int n, r;
cin >> n >> r;
if (r > n) cout << 0 << "\n";
else cout << fact[n] * inv[r] % MOD * inv[n - r] % MOD << "\n";
}
return 0;
}Python solution
import sys
MOD = 10**9 + 7
N = 10**6
data = sys.stdin.buffer.read().split()
q = int(data[0])
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
out = []
for k in range(q):
n, r = int(data[1 + 2 * k]), int(data[2 + 2 * k])
out.append(0 if r > n else fact[n] * inv[r] % MOD * inv[n - r] % MOD)
print("\n".join(map(str, out)))Java solution
import java.util.*;
import java.io.*;
public class Main {
static final long MOD = 1000000007L;
static long power(long b, long e) {
long res = 1;
b %= MOD;
while (e > 0) {
if ((e & 1) == 1) res = res * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return res;
}
public static void main(String[] args) throws IOException {
int N = 1000000;
long[] fact = new long[N + 1], inv = new long[N + 1];
fact[0] = 1;
for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2);
for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int q = (int) in.nval;
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int r = (int) in.nval;
sb.append(r > n ? 0 : fact[n] * inv[r] % MOD * inv[n - r] % MOD).append('\n');
}
System.out.print(sb);
}
}Solve nCr Modulo a Large Prime online · All practice problems