Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. C(n, r) = n! / (r! · (n−r)!). Precompute all factorials up to 10^6 once.
  2. 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