#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Cryptomath Module
# https://www.nostarch.com/crackingcodes (BSD Licensed)

from typing import Optional


def gcd(a: int, b: int) -> int:
    """Return the Greatest Common Divisor of a and b using Euclid's Algorithm"""
    while a != 0:
        a, b = b % a, a
    return b


def findModInverse(a: int, m: int) -> int:
    """
    Return the modular inverse of a % m, which is
    the number x such that a*x % m = 1
    """
    assert (
        gcd(a, m) == 1
    ), "No single mod inverse exists if a & m aren't relatively prime."
    # if gcd(a, m) != 1:
    # return None

    # Calculate using the Extended Euclidean Algorithm:
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3  # Note that // is the integer division operator
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m