1357. Multiply 64-bit Integers Without Overflow

Given non-negative 64-bit integers a and b and a modulus m, compute (a * b) mod m without ever overflowing 64-bit arithmetic. Use binary doubling so that only additions and modular reductions are needed.

Input: A JSON object {"a": <integer>, "b": <integer>, "m": <modulus>}.

Output: Return (a * b) mod m.

Examples

Input: {"a":7,"b":6,"m":10}
Output: 2
Explanation: 42 mod 10 = 2, computed without forming 42 directly.

Input: {"a":1000000000000000000,"b":1000000000000000000,"m":998244353}
Output: 433041149
Explanation: The product far exceeds 64 bits, so doubling with reduction is required.

Constraints

• 0 <= a, b <= 10^18
• 1 <= m <= 10^18

Asked by