∑MathIntermediate

Modular Inverse

Key Points

•
A modular inverse of a modulo m is a number $a_{i} n v$ such that a × $a_{i} n v$ ≡ 1 (mod m).
•
An inverse exists if and only if gcd(a, m) = 1; otherwise, modular division by a is impossible modulo m.
•
You can compute a modular inverse for any modulus using the Extended Euclidean Algorithm in O(log m) time.
•
For prime moduli p, Fermat’s little theorem gives $a^{- 1}$ ≡ $a^{p - 2}$ (mod p), computable by fast exponentiation in O(log p).
•
When many inverses modulo a prime p are needed for numbers 1..n, you can precompute them all in O(n) using inv[i] = (p − p/i) × inv[p % i] mod p.
•
Always normalize results to [0, m−1] to avoid negative residues and to compare values consistently.
•
Use modular inverses to perform division modulo p, such as computing fractions, solving linear congruences, and evaluating binomial coefficients.
•
Do not use Fermat’s method or the O(n) precompute formula when the modulus is not prime.

Prerequisites

→Greatest Common Divisor (gcd) and Euclidean Algorithm — Inverse existence depends on gcd(a, m) = 1, and EEA computes coefficients for Bézout’s identity.
→Modular Arithmetic Basics — Understanding congruences, residues, and normalization is essential for working with inverses.
→Binary Exponentiation — Needed to compute a^{p−2} mod p efficiently for Fermat’s method.
→Prime Numbers and Fields — Fermat’s theorem and the O(n) inverse precompute apply when the modulus is prime.
→Bézout’s Identity and Extended Euclidean Algorithm — Provides the theoretical and algorithmic basis for inverses under any modulus.
→Factorials and Combinatorics — Using inverses to compute nCk modulo p requires understanding factorial-based formulas.
→Integer Division and Modulo Operation in C++ — Avoiding pitfalls with negative values and ensuring correct normalization.

Detailed Explanation

Tap terms for definitions

01Overview

Hook → If you try to divide on a clock, what does “divide by 3” even mean? We can add and multiply hours easily, but division is trickier. Concept → In modular arithmetic, the modular inverse of a number a modulo m is the value that “undoes” multiplication by a, so that multiplying them gives 1 under modulo m. Not every number has such an inverse—only those that are coprime with the modulus. Example → Modulo 12, 5 has an inverse because 5 × 5 = 25 ≡ 1 (mod 12), so 5^{-1} ≡ 5. But 4 has no inverse modulo 12 because any multiple of 4 is even, so it can never be congruent to 1 (an odd number) modulo 12.

Practically, modular inverses allow you to perform division in modulo arithmetic, which is essential in competitive programming for tasks like computing fractions, solving linear equations ax ≡ b (mod m), and evaluating combinatorial values like nCk modulo a prime. There are three standard ways to compute them: (1) Extended Euclidean Algorithm (works for any modulus if gcd(a, m) = 1), (2) Fermat’s little theorem using fast exponentiation when the modulus is prime, and (3) a linear-time precomputation for inverses of 1..n modulo a prime. These tools let you choose between flexibility, speed for single queries, and efficiency for bulk queries.

02Intuition & Analogies

Think of an inverse as an “undo” button. Multiplying by a scrambles a number in a predictable way; multiplying by a^{-1} unscrambles it back to where you started, modulo m. On a 12-hour clock, adding 5 hours is like multiplying by 5 in some contexts; the inverse tells you how to get back to 12 (the identity). If multiplying by a is like turning a combination lock by a steps, multiplying by a^{-1} is turning it a different number of steps to return to the start.

When the modulus is prime, every nonzero number has an inverse—this is like working in a field where division always works (except by zero). That’s why using primes like 10^9+7 is so popular: you can always divide by any nonzero a. Fermat’s little theorem says that if you keep multiplying a by itself p−1 times, you loop back to 1, which means the product of p−2 copies of a behaves like an “undo” for a.

For the Extended Euclidean Algorithm, imagine trying to combine multiples of a and m to make 1. If you can write ax + my = 1, then reducing both sides modulo m kills the my term (it becomes 0 mod m), leaving ax ≡ 1 (mod m). That x is the inverse you wanted. The algorithm efficiently finds such x and y using repeated division (like peeling an onion layer by layer), and it works for any modulus as long as a and m are coprime.

The O(n) precompute formula is like caching lots of small undo buttons all at once, reusing previously found inverses to get new ones cheaply. If you need to divide by many different numbers frequently, paying a one-time linear cost makes every later division O(1).

03Formal Definition

Given integers a and m with

m \geq 2

, a modular inverse of a modulo m is an integer

a^{- 1}

satisfying a

a^{- 1}

\equiv

(mod m)

. Existence condition:

a^{- 1}

exists if and only if

g cd

(a, m) = 1. Uniqueness: if an inverse exists, it is unique modulo m (there is exactly one residue class modulo m with this property). By Bézout’s identity, there exist integers x, y such that ax + my =

g cd

(a, m). When

g cd

(a, m) = 1, this becomes ax +

m y = 1

. Reducing modulo m yields ax

\equiv

(mod m)

, so x is a modular inverse of a. The Extended Euclidean Algorithm finds such x and y in O(

lo g

m) time. For a prime modulus p and a not divisible by p, Fermat’s little theorem gives

a^{p - 1}

\equiv

(mod p)

. Multiplying both sides by

a^{- 1}

implies

a^{p - 2}

\equiv

a^{- 1}

(mod p)

. Thus,

a^{p - 2}

(computed via binary exponentiation) is the inverse. More generally, Euler’s theorem states that for

g cd

(a, m) = 1,

a^{φ (m)}

\equiv

(mod m)

, implying

a^{φ (m) - 1}

is an inverse. However, computing

φ

(m) may not be practical for large m. For prime p, the inverses of 1..n (

n < p

) satisfy inv[1] = 1 and inv[i] = (p − p/i) × inv[p % i]

mod

p, deriving from dividing i × inv[i] ≡ 1 and splitting i as (p − (p % i)) to reuse inv[p % i].

04When to Use

Use a modular inverse whenever you need to divide under a modulus. Common cases include:

Solving linear congruences ax ≡ b (mod m): if d = gcd(a, m) = 1, then x ≡ a^{-1} b (mod m). If d > 1 and d | b, reduce to modulus m/d; otherwise no solutions.
Computing fractions modulo a prime p: to compute p/q mod p, use p × q^{-1} mod p with q ≠ 0 mod p.
Combinatorics under prime moduli: nCk mod p = n! × (k!)^{-1} × ((n−k)!)^{-1} mod p. Precomputing factorials and inverse factorials makes many queries O(1).
Dynamic programming or prefix sums where you need to divide by counts or probabilities modulo p (e.g., averaging or normalizing values modulo a prime).
Polynomial/FFT-like algorithms over finite fields: dividing coefficients or normalizing by sizes requires inverses when the modulus is prime.

Pick the method based on workload: use Extended Euclid for arbitrary modulus or one-off queries; use Fermat’s method for prime modulus and occasional queries; use O(n) precomputation for many inversions in a known range modulo a prime.

⚠️Common Mistakes

• Using Fermat’s little theorem with a composite modulus. a^{p−2} only yields an inverse modulo a prime p (or in general in a field); for composite m it can fail even if gcd(a, m) = 1. • Forgetting the coprimality check. If gcd(a, m) ≠ 1, no inverse exists. Calling an inverse function without checking can produce garbage values. • Not normalizing negatives. Extended Euclid may return a negative x; always map to [0, m−1] via (x % m + m) % m. • Dividing by zero modulo p. 0 has no inverse. Similarly, if a ≡ 0 (mod p), inv(a) is undefined. • Overflow during modular exponentiation. Using 64-bit multiplication may overflow when mod is near 1e18; use 128-bit intermediates (__int128) or modular multiplication routines. • Misusing the O(n) precompute formula for non-prime moduli. The recurrence inv[i] = (p − p/i) × inv[p % i] works in fields (prime p); it does not generally hold for composite moduli. • Forgetting that inverse is unique modulo m, not as an absolute integer. Different-looking answers that differ by multiples of m are the same inverse class. • Using Euler’s theorem blindly. While a^{\varphi(m)−1} is an inverse when gcd(a, m) = 1, computing \varphi(m) requires factorization, which is often slower than Extended Euclid.

Key Formulas

Modular Inverse Definition

a \cdot a^{- 1} \equiv 1 (mod m)

Explanation: This states that $a^{- 1}$ is the number that multiplies with a to yield 1 under modulus m. It is the modular equivalent of division by a.

Existence Criterion

g cd (a, m) = 1 ⟺ \exists a^{- 1} (mod m)

Explanation: An inverse exists exactly when a and m are coprime. If they share a factor, you cannot reach 1 as a multiple of a modulo m.

Bézout’s Identity

a x + m y = g cd (a, m)

Explanation: For integers a and m, there exist x and y satisfying this linear combination. When the gcd is 1, x is a modular inverse of a modulo m.

Fermat’s Little Theorem

a^{p - 1} \equiv 1 (mod p)

Explanation: For prime p and a not divisible by p, raising a to p−1 cycles back to 1. This underlies the inverse formula $a^{p - 2}$ (mod p).

Fermat Inverse

a^{- 1} \equiv a^{p - 2} (mod p)

Explanation: Multiplying both sides of $a^{p - 1}$ ≡ 1 by $a^{- 1}$ gives $a^{p - 2}$ ≡ $a^{- 1}$ . We compute $a^{p - 2}$ via binary exponentiation.

Euler’s Theorem

a^{φ (m)} \equiv 1 (mod m) (g cd (a, m) = 1)

Explanation: Generalizes Fermat’s theorem to composite moduli using Euler’s totient $φ (m) .$ It implies $a^{φ (m) - 1}$ is an inverse, though $φ (m)$ may be hard to compute.

O(n) Inverse Precomputation (Prime p)

inv [1] = 1, inv [i] = (p - ⌊ p / i ⌋) \cdot inv [p mod i] mod p

Explanation: This recurrence computes all inverses 1..n modulo a prime in linear time by reusing already computed inverses. It is widely used in competitive programming.

Extended Euclid Complexity

T_{EEA} (m) = O (lo g m)

Explanation: The extended Euclidean algorithm runs in logarithmic time in the size of the modulus. It is efficient for arbitrary moduli.

Binary Exponentiation Complexity

T_{pow} (p) = O (lo g p)

Explanation: Fast exponentiation computes $a^{p - 2}$ using O(log p) multiplications. It’s ideal for single or few inverse computations under a prime modulus.

Binomial Coefficient via Inverses

(k n) mod p = n! \cdot (k!)^{- 1} \cdot ((n - k)!)^{- 1} mod p

Explanation: Computes combinations under a prime modulus using factorials and their inverses. After preprocessing, each query is O(1).

Normalization

x mod m = ((x mod m) + m) mod m

Explanation: This ensures results lie in [0, m−1], handling negative intermediate values correctly. It avoids sign issues in modular arithmetic.

Complexity Analysis

There are three main computational strategies. 1) Extended Euclidean Algorithm (EEA): Computing the inverse via EEA takes O(log m) arithmetic steps, where m is the modulus. Each step uses division with remainder, and the sequence of remainders decreases quickly. Space usage is O(1) beyond call stack depth or O(log m) in recursive form. This method works for any modulus when gcd(a, m) = 1 and avoids exponentiation. 2) Fermat’s Little Theorem with Binary Exponentiation (prime modulus p): Computing

a^{p - 2}

mod p takes O(log p) multiplications using exponentiation by squaring. With 64-bit types and large p (e.g., 10^9+7), intermediate products should use 128-bit (__int128) to prevent overflow before reduction. Space usage is O(1). This approach is clean and fast for single inverses under a prime modulus. 3) O(n) Precomputation of inverses for 1..n (prime modulus p): Building an array inv[1..n] uses a single pass with the recurrence inv[i] = (p − p/i) × inv[p % i] mod p, taking O(n) time and O(n) space. After preprocessing, each inverse query for i in [1..n] is O(1). This is ideal when many divisions by small integers are needed, such as factorial inverses or dynamic programs with frequent normalization. In practice: choose EEA for arbitrary moduli or when p may be composite; choose Fermat for prime moduli when queries are few; choose precompute when you need many inverses with fixed prime p. For binomial coefficients with many queries, precompute factorials and inverse factorials in O(n); each nCk query is O(1).

Code Examples

Modular Inverse with Extended Euclidean Algorithm (works for any modulus)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Extended Euclidean Algorithm
5 // Finds x, y such that a*x + b*y = gcd(a, b)
6 long long ext_gcd(long long a, long long b, long long &x, long long &y) {
7     if (b == 0) { x = (a >= 0 ? 1 : -1); y = 0; return llabs(a); }
8     long long x1, y1;
9     long long g = ext_gcd(b, a % b, x1, y1);
10     x = y1;
11     y = x1 - (a / b) * y1;
12     return g;
13 }
14 
15 // Returns modular inverse of a modulo m if it exists; otherwise returns -1
16 long long mod_inverse_any(long long a, long long m) {
17     a %= m; if (a < 0) a += m;
18     long long x, y;
19     long long g = ext_gcd(a, m, x, y);
20     if (g != 1) return -1; // inverse does not exist
21     long long inv = x % m;
22     if (inv < 0) inv += m;
23     return inv;
24 }
25 
26 int main() {
27     ios::sync_with_stdio(false);
28     cin.tie(nullptr);
29 
30     // Demo: read pairs (a, m) and print inverse or -1 if it doesn't exist
31     vector<pair<long long,long long>> tests = {
32         {5, 12},   // inverse exists: 5
33         {4, 12},   // no inverse
34         {-3, 11},  // inverse exists
35         {25, 36}   // inverse exists since gcd(25,36)=1
36     };
37 
38     for (auto [a, m] : tests) {
39         long long inv = mod_inverse_any(a, m);
40         cout << "a=" << a << ", m=" << m << ": inv=" << inv;
41         if (inv != -1) {
42             long long check = (__int128)( (a % m + m) % m ) * inv % m;
43             cout << ", a*inv % m=" << check;
44         }
45         cout << "\n";
46     }
47     return 0;
48 }
49

This program computes modular inverses for arbitrary moduli using the Extended Euclidean Algorithm. If gcd(a, m) = 1, the coefficient x from Bézout’s identity is the inverse modulo m. Results are normalized to [0, m−1], and a simple product check verifies correctness.

Time: O(log m)Space: O(1)

Modular Inverse via Fermat’s Little Theorem (prime modulus)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Safe modular multiplication using 128-bit intermediate
5 static inline long long mul_mod(long long a, long long b, long long mod) {
6     return (long long)((__int128)a * b % mod);
7 }
8 
9 long long pow_mod(long long a, long long e, long long mod) {
10     a %= mod; if (a < 0) a += mod;
11     long long res = 1 % mod;
12     while (e > 0) {
13         if (e & 1) res = mul_mod(res, a, mod);
14         a = mul_mod(a, a, mod);
15         e >>= 1;
16     }
17     return res;
18 }
19 
20 // Inverse modulo prime p using Fermat: a^(p-2) mod p; returns -1 if a % p == 0
21 long long mod_inverse_prime(long long a, long long p) {
22     a %= p; if (a < 0) a += p;
23     if (a == 0) return -1; // no inverse for 0
24     return pow_mod(a, p - 2, p);
25 }
26 
27 int main() {
28     ios::sync_with_stdio(false);
29     cin.tie(nullptr);
30 
31     const long long p = 1000000007LL; // prime modulus
32     vector<long long> vals = {1, 2, 3, 123456789, p - 1};
33 
34     for (long long a : vals) {
35         long long inv = mod_inverse_prime(a, p);
36         long long check = (inv == -1 ? -1 : mul_mod(a % p, inv, p));
37         cout << "a=" << a << ", inv=" << inv << ", a*inv % p=" << check << "\n";
38     }
39 
40     // Example: compute (numerator / denominator) mod p
41     long long numerator = 987654321LL;
42     long long denominator = 1234567LL;
43     long long inv_den = mod_inverse_prime(denominator, p);
44     if (inv_den == -1) cout << "Division undefined (denominator % p == 0)\n";
45     else cout << "(numerator/denominator) % p = " << mul_mod(numerator % p, inv_den, p) << "\n";
46 
47     return 0;
48 }
49

This program computes inverses modulo a prime p using Fermat’s little theorem with binary exponentiation. It safely multiplies using 128-bit intermediates to avoid overflow and demonstrates modular division by multiplying with the inverse.

Time: O(log p) per inverseSpace: O(1)

O(n) Precomputation of inverses 1..n modulo a prime

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Precompute inverses of 1..n modulo prime p in O(n)
5 vector<long long> precompute_inverses(int n, long long p) {
6     vector<long long> inv(n + 1, 0);
7     if (n >= 1) inv[1] = 1;
8     for (int i = 2; i <= n; ++i) {
9         // inv[i] = (p - p/i) * inv[p % i] % p
10         inv[i] = (p - (p / i)) * inv[p % i] % p;
11     }
12     return inv;
13 }
14 
15 int main() {
16     ios::sync_with_stdio(false);
17     cin.tie(nullptr);
18 
19     const long long p = 1000000007LL; // prime
20     int n = 20;                       // example range
21 
22     vector<long long> inv = precompute_inverses(n, p);
23     for (int i = 1; i <= n; ++i) {
24         cout << "inv[" << i << "] = " << inv[i] << "\n";
25     }
26 
27     // Verify: i * inv[i] % p == 1
28     bool ok = true;
29     for (int i = 1; i <= n; ++i) {
30         long long check = ( (__int128)i * inv[i]) % p;
31         if (check != 1) { ok = false; break; }
32     }
33     cout << (ok ? "All verified" : "Verification failed") << "\n";
34 
35     // Example usage: divide elements by their index modulo p
36     vector<long long> arr = {5, 10, 15, 20, 25};
37     for (int i = 0; i < (int)arr.size(); ++i) {
38         long long div_by = i + 1; // divide by (i+1)
39         long long res = ( (__int128)(arr[i] % p + p) % p ) * inv[div_by] % p;
40         cout << "arr[" << i << "]/" << div_by << " mod p = " << res << "\n";
41     }
42 
43     return 0;
44 }
45

This code precomputes inverses of 1..n modulo a prime p in linear time using the standard recurrence. It verifies correctness and demonstrates fast modular division by small integers using the precomputed inverses.

Time: O(n) preprocessing; O(1) per inverse lookupSpace: O(n)

Binomial Coefficients nCk modulo a prime using factorials and inverse factorials

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 static inline long long mul_mod(long long a, long long b, long long mod) {
5     return (long long)((__int128)a * b % mod);
6 }
7 
8 long long pow_mod(long long a, long long e, long long mod) {
9     a %= mod; if (a < 0) a += mod;
10     long long res = 1 % mod;
11     while (e > 0) {
12         if (e & 1) res = mul_mod(res, a, mod);
13         a = mul_mod(a, a, mod);
14         e >>= 1;
15     }
16     return res;
17 }
18 
19 struct Comb {
20     int N; long long p; vector<long long> fact, invfact;
21     Comb(int N, long long p): N(N), p(p), fact(N+1), invfact(N+1) {
22         fact[0] = 1;
23         for (int i = 1; i <= N; ++i) fact[i] = mul_mod(fact[i-1], i, p);
24         // Compute invfact[N] using Fermat, then go downwards to fill all invfacts
25         invfact[N] = pow_mod(fact[N], p - 2, p);
26         for (int i = N; i >= 1; --i) invfact[i-1] = mul_mod(invfact[i], i, p);
27     }
28     long long nCk(int n, int k) const {
29         if (k < 0 || k > n) return 0;
30         return mul_mod(fact[n], mul_mod(invfact[k], invfact[n-k], p), p);
31     }
32 };
33 
34 int main() {
35     ios::sync_with_stdio(false);
36     cin.tie(nullptr);
37 
38     const long long p = 1000000007LL;
39     int N = 1000000; // Precompute up to 1e6
40     Comb C(N, p);
41 
42     // Example queries
43     vector<pair<int,int>> qs = {{5,2}, {10,3}, {1000000, 500000}};
44     for (auto [n,k] : qs) {
45         cout << "C(" << n << "," << k << ") mod p = " << C.nCk(n,k) << "\n";
46     }
47 
48     return 0;
49 }
50

We precompute factorials and inverse factorials modulo a prime p. Using invfact[N] = fact[N]^{p−2} mod p and a downward pass, we obtain O(1) queries for nCk, which relies on modular inverses to perform division in the factorial formula.

Time: O(N) preprocessing; O(1) per nCk querySpace: O(N)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Extended Euclidean Algorithm
5	// Finds x, y such that ax + by = gcd(a, b)
6	long long ext_gcd(long long a, long long b, long long &x, long long &y) {
7	if (b == 0) { x = (a >= 0 ? 1 : -1); y = 0; return llabs(a); }
8	long long x1, y1;
9	long long g = ext_gcd(b, a % b, x1, y1);
10	x = y1;
11	y = x1 - (a / b) * y1;
12	return g;
13	}
14
15	// Returns modular inverse of a modulo m if it exists; otherwise returns -1
16	long long mod_inverse_any(long long a, long long m) {
17	a %= m; if (a < 0) a += m;
18	long long x, y;
19	long long g = ext_gcd(a, m, x, y);
20	if (g != 1) return -1; // inverse does not exist
21	long long inv = x % m;
22	if (inv < 0) inv += m;
23	return inv;
24	}
25
26	int main() {
27	ios::sync_with_stdio(false);
28	cin.tie(nullptr);
29
30	// Demo: read pairs (a, m) and print inverse or -1 if it doesn't exist
31	vector<pair<long long,long long>> tests = {
32	{5, 12}, // inverse exists: 5
33	{4, 12}, // no inverse
34	{-3, 11}, // inverse exists
35	{25, 36} // inverse exists since gcd(25,36)=1
36	};
37
38	for (auto [a, m] : tests) {
39	long long inv = mod_inverse_any(a, m);
40	cout << "a=" << a << ", m=" << m << ": inv=" << inv;
41	if (inv != -1) {
42	long long check = (__int128)( (a % m + m) % m ) * inv % m;
43	cout << ", a*inv % m=" << check;
44	}
45	cout << "\n";
46	}
47	return 0;
48	}
49

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Safe modular multiplication using 128-bit intermediate
5	static inline long long mul_mod(long long a, long long b, long long mod) {
6	return (long long)((__int128)a * b % mod);
7	}
8
9	long long pow_mod(long long a, long long e, long long mod) {
10	a %= mod; if (a < 0) a += mod;
11	long long res = 1 % mod;
12	while (e > 0) {
13	if (e & 1) res = mul_mod(res, a, mod);
14	a = mul_mod(a, a, mod);
15	e >>= 1;
16	}
17	return res;
18	}
19
20	// Inverse modulo prime p using Fermat: a^(p-2) mod p; returns -1 if a % p == 0
21	long long mod_inverse_prime(long long a, long long p) {
22	a %= p; if (a < 0) a += p;
23	if (a == 0) return -1; // no inverse for 0
24	return pow_mod(a, p - 2, p);
25	}
26
27	int main() {
28	ios::sync_with_stdio(false);
29	cin.tie(nullptr);
30
31	const long long p = 1000000007LL; // prime modulus
32	vector<long long> vals = {1, 2, 3, 123456789, p - 1};
33
34	for (long long a : vals) {
35	long long inv = mod_inverse_prime(a, p);
36	long long check = (inv == -1 ? -1 : mul_mod(a % p, inv, p));
37	cout << "a=" << a << ", inv=" << inv << ", a*inv % p=" << check << "\n";
38	}
39
40	// Example: compute (numerator / denominator) mod p
41	long long numerator = 987654321LL;
42	long long denominator = 1234567LL;
43	long long inv_den = mod_inverse_prime(denominator, p);
44	if (inv_den == -1) cout << "Division undefined (denominator % p == 0)\n";
45	else cout << "(numerator/denominator) % p = " << mul_mod(numerator % p, inv_den, p) << "\n";
46
47	return 0;
48	}
49

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Precompute inverses of 1..n modulo prime p in O(n)
5	vector<long long> precompute_inverses(int n, long long p) {
6	vector<long long> inv(n + 1, 0);
7	if (n >= 1) inv[1] = 1;
8	for (int i = 2; i <= n; ++i) {
9	// inv[i] = (p - p/i) * inv[p % i] % p
10	inv[i] = (p - (p / i)) * inv[p % i] % p;
11	}
12	return inv;
13	}
14
15	int main() {
16	ios::sync_with_stdio(false);
17	cin.tie(nullptr);
18
19	const long long p = 1000000007LL; // prime
20	int n = 20; // example range
21
22	vector<long long> inv = precompute_inverses(n, p);
23	for (int i = 1; i <= n; ++i) {
24	cout << "inv[" << i << "] = " << inv[i] << "\n";
25	}
26
27	// Verify: i * inv[i] % p == 1
28	bool ok = true;
29	for (int i = 1; i <= n; ++i) {
30	long long check = ( (__int128)i * inv[i]) % p;
31	if (check != 1) { ok = false; break; }
32	}
33	cout << (ok ? "All verified" : "Verification failed") << "\n";
34
35	// Example usage: divide elements by their index modulo p
36	vector<long long> arr = {5, 10, 15, 20, 25};
37	for (int i = 0; i < (int)arr.size(); ++i) {
38	long long div_by = i + 1; // divide by (i+1)
39	long long res = ( (__int128)(arr[i] % p + p) % p ) * inv[div_by] % p;
40	cout << "arr[" << i << "]/" << div_by << " mod p = " << res << "\n";
41	}
42
43	return 0;
44	}
45