Finding inverse

def modular_inverse(a, M):
    # Helper function to implement the Extended Euclidean Algorithm
    def extended_gcd(a, b):
        if b == 0:
            return a, 1, 0
        gcd, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y

    gcd, x, _ = extended_gcd(a, M)
    
    # If gcd is not 1, the modular inverse does not exist
    if gcd != 1:
        return -1
    
    # Make sure x is positive and within the range (0, M)
    return x % M

# Read input
import sys
input = sys.stdin.read
a, M = map(int, input().split())

# Compute the modular inverse
result = modular_inverse(a, M)

# Output the result
print(result)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED