from typing import Dict


def get_all_mod_inverse_dict(m: int, max_n: int) -> Dict[int, int]:
    """
    Computes a^-1 mod m for all a in [1, a-1]
    https://cp-algorithms.com/algebra/module-inverse.html#mod-inv-all-num

    Taking the key * value mod m for each key value would result in 1
    """
    dc_inv = {1: 1}
    for i in range(2, max_n+1):
        dc_inv[i] = m - (m // i) * dc_inv[m % i] % m
    return dc_inv