Modular Combinatorics

Many counting tasks ask for binomial coefficients modulo a prime. Factorial and inverse-factorial tables turn each query into a few multiplications after preprocessing. The crucial restriction is n<p: once n reaches the prime, n! is zero modulo p and cannot be inverted. This lesson fixes p=1000000007 and a preprocessing maximum below it, clearly separating this fast method from more general binomial arithmetic.

Prerequisites: Factorials; modular inverses; Binary Exponentiation. The counting interpretation is developed further in Combinations.

Build the idea

1. 1. Start from the integer counting formula

   Choosing k of n distinct objects without order gives C(n,k)=n!/(k!(n−k)!). The denominator compensates for ordering within selected and unselected groups. As an integer formula it is exact; modulo p, each denominator factor must be invertible before division can be replaced by inverse multiplication.

   $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$$

2. 2. Build factorials once

   fact[0]=1 and fact[i]=fact[i−1]·i mod p. If the largest query n is N<p, every factor from 1 through N is nonzero modulo p, so every stored factorial has an inverse. The program’s N≤10^6 is comfortably below the fixed prime. This is a mathematical prerequisite, not just a memory setting.

3. 3. Obtain all inverse factorials efficiently

   Compute invFact[N]=fact[N]^(p−2) mod p using Fermat. Then invFact[i−1]=invFact[i]·i mod p, because 1/(i−1)!=i/i!. A single exponentiation plus a backward linear pass replaces an exponentiation at every entry. Query C(n,k)=fact[n]·invFact[k]·invFact[n−k] mod p, reducing after each product.

4. 4. Work sample queries

   C(5,2)=120/(2·6)=10; C(5,0)=1 because the empty selection is unique. If k<0 or k>n, there are no selections and the program returns zero before indexing the tables. The query’s n itself must lie in the preprocessed interval; an out-of-range n is an input-contract violation, not a reason to index arbitrary storage.

5. 5. Know what changes at or beyond p

   For n≥p, fact[n]≡0 and Fermat exponentiation of zero does not create an inverse. Some binomial coefficients are nevertheless nonzero modulo p, so returning zero universally is wrong. Lucas-type methods or prime-factor-aware factorial techniques address other regimes; composite moduli also require different reasoning because nonzero factorial factors may be noninvertible. Use this table only under its stated prime and size assumptions.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Know what changes at or beyond p For n≥p, fact[n]≡0 and Fermat exponentiation of zero
// does not create an inverse.
#include<iostream>
#include<vector>
using ll=long long;
ll power(ll a,unsigned long long exponent,ll mod){
    a=(a%mod+mod)%mod;
    ll result=1%mod;
    while(exponent>0){
        if(exponent&1ULL){
            result=result*a%mod;
        }
        a=a*a%mod;
        exponent>>=1;
    }
    return result;
}
int main(){
    int N,q;
    std::cin>>N>>q;
    const ll MOD=1000000007;
    std::vector<ll>factorial(N+1,1),inverseFactorial(N+1,1);
    for(int i=1;i<=N;++i){
        factorial[i]=factorial[i-1]*i%MOD;
    }
    inverseFactorial[N]=power(factorial[N],MOD-2,MOD);
    for(int i=N;i>=1;--i){
        inverseFactorial[i-1]=inverseFactorial[i]*i%MOD;
    }
    while(q--){
        int n,k;
        std::cin>>n>>k;
        if(k<0||k>n){
            std::cout<<0<<'\n';
        }
        else{
            std::cout<<factorial[n]*inverseFactorial[k]%MOD*inverseFactorial[n-k]%MOD<<'\n';
        }
    }
}

Complexity analysis

O(N+log p) preprocessing time, O(N) memory and O(1) per binomial query, fixed p=1000000007. Products of two reduced residues fit long long; reduce before multiplying the third factor. Query output adds O(q) total work. N≤10^6<p is explicitly required.

Example input and output

Read N q (0≤N≤10^6), then q pairs n k with 0≤n≤N and k fitting int. Output C(n,k) modulo 1000000007, zero if k outside 0..n.

Input

5 3
5 2
5 0
3 7

Output

10
1
0

There are ten two-element selections from five, one empty selection and no seven-element selection from three.

Practical applications

Use for many choose queries, lattice-path counts and combinatorial DP under a suitable prime. Pascal DP works with any positive modulus but costs more per preprocessed n,k range. Exact small binomials and prime-factor-aware large-n methods solve different regimes.

Check your understanding

Why require N<p for this factorial-table method?

Put it into practice

Compare every result for n≤30 with Pascal’s recurrence.