The Inverse Hunter: Find the Modular Multiplicative Inverse

In the cryptographic workshops of Prime City, the Royal Cipher Master needs modular inverses to decode secret messages. The modular multiplicative inverse of a modulo m is a number x such that (a * x) mod m = 1. It exists if and only if gcd(a, m) = 1. "The Extended Euclidean Algorithm is your weapon," the Cipher Master says, sliding a quill across the desk. "It finds gcd(a, m) and, as a byproduct, the coefficients x and y such that a*x + m*y = gcd(a, m). When the gcd is 1, x is the modular inverse." Given integers a and m, find the modular multiplicative inverse of a modulo m. If the inverse does not exist (gcd(a, m) != 1), output -1. The inverse must be in the range [0, m-1]. The Cipher Master's constraints: 1 <= a, m <= 10^9 From the Cipher Master's verified scrolls: Input: 3 11 Output: 4 Input: 10 17 Output: 12 The cipher locks are intricate, and the messages are urgent. Find the inverse, and the kingdom's communications will be secure.