Implement 64-bit modular exponentiation safely

Implement a function to compute (a^b) mod m where 0 ≤ a,b < 2^61−1 and 1 ≤ m < 2^61−1 using only 64-bit operations without overflow. Provide implementations for fast modular multiplication that avoids overflow and fast modular exponentiation. Include comprehensive tests and analyze the time and space complexity.

64-bit Safe Modular Exponentiation

Implement a function modPow(a, b, m) that computes (a^b) mod m for 0 ≤ a, b < 2^61−1 and 1 ≤ m < 2^61−1.

The challenge is doing this with 64-bit operations without overflow. A naive (x * y) % m overflows a 64-bit integer when m is near 2^61, because the product x * y can be as large as ~2^122. Your implementation must:

1. Provide an overflow-safe modular multiplication mulmod(x, y, m) = (x*y) mod m where the inputs are already reduced mod m (so x, y < m < 2^61).
2. Use fast (binary / square-and-multiply) modular exponentiation on top of it.

Return the value of (a^b) mod m.

Notes:

• a^0 = 1 for any a (including 0^0 = 1, by convention).
• When m = 1, every value is congruent to 0, so the answer is 0.

In languages with native big integers (Python, JS BigInt) you may rely on them, but the intermediate product must never require more than what a 64-bit/128-bit-emulated multiply can represent. In C++/Java you must avoid overflowing a 64-bit signed/unsigned integer in the multiply step.

Constraints

• 0 ≤ a < 2^61−1
• 0 ≤ b < 2^61−1
• 1 ≤ m < 2^61−1
• Use only 64-bit operations (or a 128-bit-emulated multiply); no intermediate value may overflow a 64-bit integer in C++/Java
• 0^0 is defined as 1

Examples

Example 1

Input: (2, 10, 1000)
Output: 24

Explanation: 2^10 = 1024, and 1024 mod 1000 = 24.

Example 2

Input: (3, 0, 7)
Output: 1

Explanation: Any base to the 0 power is 1, and 1 mod 7 = 1.

Hints

1. Square-and-multiply: process the exponent bit by bit. Keep result and base; whenever the current low bit of the exponent is 1, multiply result by base (mod m); always square base (mod m) and shift the exponent right.
2. The dangerous step is the multiply (xy) % m, not the exponentiation loop. When m is near 2^61, xy is near 2^122 and overflows 64 bits. Use a 128-bit product (unsigned __int128 in C++) or a binary double-and-add mulmod: result += x then x += x, each reduced mod m, which keeps every value below 2*m < 2^62.
3. Handle the corner cases first: if m == 1 the answer is 0; reduce a mod m before the loop; b == 0 must yield 1 (the loop naturally leaves result = 1).