Introduction

1000000007 appears constantly in competitive programming because it is large, prime, and small enough to fit comfortably in standard integer types. Once you understand the small set of modular-arithmetic rules behind it, many seemingly different problems reduce to the same patterns.

Why This Modulus Is So Common

The number 1000000007 is prime, which makes modular inverses easy for non-zero values. It is also close to 10^9, so it is large enough to reduce collision risk and keep many combinatorics answers meaningful after reduction.

Most importantly, applying the modulus during intermediate steps prevents values from growing beyond the limits of normal integer arithmetic.

The Core Rules

For a modulus MOD, these identities are the foundation:

• '(a + b) % MOD = ((a % MOD) + (b % MOD)) % MOD'
• '(a - b) % MOD = ((a % MOD) - (b % MOD) + MOD) % MOD'
• '(a * b) % MOD = ((a % MOD) * (b % MOD)) % MOD'

The big practical lesson is to reduce early and often. Do not wait until the very end if intermediate values can overflow.

1MOD = 1_000_000_007
2
3a = 10**18
4b = 10**18
5
6print((a % MOD) * (b % MOD) % MOD)

Fast Power Is Essential

Exponentiation is where beginners often lose performance. Repeated multiplication takes too long for large exponents, so use binary exponentiation.

1MOD = 1_000_000_007
2
3
4def mod_pow(base, exp, mod=MOD):
5    result = 1
6    base %= mod
7
8    while exp > 0:
9        if exp & 1:
10            result = (result * base) % mod
11        base = (base * base) % mod
12        exp >>= 1
13
14    return result
15
16
17print(mod_pow(2, 10))

This runs in O(log exp) time instead of O(exp).

Division Means Modular Inverse

Normal division does not exist directly under a modulus. When the modulus is prime and the value is not divisible by it, divide by multiplying with the modular inverse.

Using Fermat’s little theorem, the inverse of x modulo MOD is x^(MOD - 2) mod MOD.

1MOD = 1_000_000_007
2
3
4def mod_inv(x, mod=MOD):
5    return mod_pow(x, mod - 2, mod)
6
7
8numerator = 10
9denominator = 4
10answer = numerator * mod_inv(denominator) % MOD
11print(answer)

That is the pattern behind many combination and probability-style problems.

A Typical Combinatorics Pattern

When you need many nCr queries, precompute factorials and inverse factorials once.

1MOD = 1_000_000_007
2MAX_N = 100000
3
4fact = [1] * (MAX_N + 1)
5inv_fact = [1] * (MAX_N + 1)
6
7for i in range(1, MAX_N + 1):
8    fact[i] = fact[i - 1] * i % MOD
9
10inv_fact[MAX_N] = mod_inv(fact[MAX_N])
11for i in range(MAX_N, 0, -1):
12    inv_fact[i - 1] = inv_fact[i] * i % MOD
13
14
15def ncr(n, r):
16    if r < 0 or r > n:
17        return 0
18    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
19
20
21print(ncr(5, 2))

This turns many queries into constant-time lookups after linear preprocessing.

Think About Negative Values Too

Subtraction can produce negative intermediate values. In languages like C++ and Java, always normalize the result back into the desired range.

1MOD = 1_000_000_007
2x = 3
3y = 5
4print((x - y + MOD) % MOD)

That pattern avoids surprises when the raw subtraction would be negative.

Common Pitfalls

• Taking the modulus only at the end can allow overflow before the final reduction.
• Using ordinary division instead of a modular inverse gives the wrong answer.
• Forgetting to normalize subtraction can leave negative values in the result.
• Recomputing powers or factorials from scratch inside every query leads to time-limit issues.
• Applying Fermat-based inverses when the modulus is not prime is incorrect.

Summary

• '1000000007 is popular because it is prime and practical for large-number problems.'
• Reduce after addition, subtraction, and multiplication to keep values safe.
• Use binary exponentiation for fast powers.
• Replace division with multiplication by a modular inverse when the conditions allow it.
• Precomputation is the standard trick for repeated combinatorics queries.