BigInt & Modulo Calculator

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.

Worked Example: Three Tabs, One Modulus

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).

Accuracy, Limits and the Two Failure Modes

• All arithmetic is BigInt, so there is no upper bound on the values you can type and no silent wraparound. The C++ snippets use __int128 casts to get the same safety in a compiled solution.
• An inverse exists only when the value and the modulus are coprime. When they are not, the tool reports No inverse (gcd ≠ 1) rather than returning a plausible wrong number.
• The binomial is computed as a product of r terms divided by r factorial through a modular inverse, so it requires r factorial to be invertible. That holds whenever m is prime and larger than n, which covers 1000000007 and 998244353.
• The two ways that can fail are reported separately: 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.
• A modulus of 1 correctly returns 0 for exponentiation, since every value is congruent to 0 modulo 1.
• The nCr routine uses the smaller of r and n minus r, so C(1000, 995) costs 5 iterations rather than 995.
• The included nCr snippet uses precomputed factorials and does not implement Lucas' theorem, which the comment says outright. For n near 10 to the 18th with a small prime you need the Lucas version instead.