Compute modular inverse, fast power modulo, and nCr mod p using BigInt precision. One-click C++ snippet output for each operation.
Every competitive problem that says “output the answer modulo 1000000007” is asking for three operations: fast exponentiation, a modular inverse, and a binomial coefficient built from the first two. The Modular Arithmetic Calculator computes all three in native BigInt, so the intermediate products that overflow a 64-bit integer simply do not here.
Exponentiation is binary: square the base, halve the exponent, multiply into the result whenever the exponent is odd. That turns an exponent of 987654321 into about 30 multiplications rather than a billion.
The inverse comes from the extended Euclidean algorithm rather than from Fermat's little theorem, which means it works for any modulus coprime to the value instead of requiring a prime one. Each tab carries a matching C++ snippet below the result, and nothing is transmitted.
The defaults are a of 123456789, b of 987654321 and m of 1000000007. The a^b mod m tab returns 652541198. Switch to a⁻¹ mod m and the inverse of 123456789 is 18633540, which you can verify by multiplying the two together modulo m and getting 1. The nCr mod m tab with n of 20 and r of 5 returns 15504, which is small enough that the modulus never bites and the answer is simply C(20,5).
__int128 casts to get the same safety in a compiled solution.No inverse (gcd ≠ 1) rather than returning a plausible wrong number.too-large when r exceeds 100,000 and the loop would freeze the tab, and no-inverse when the modulus is composite or too small. Collapsing both into one message hid genuine bugs.652541198C++ Implementation
// Fast modular exponentiation
long long modpow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (__int128)result * base % mod;
base = (__int128)base * base % mod;
exp >>= 1;
}
return result;
}