from random import SystemRandom # random number generator
rand = SystemRandom ()   # strong random number generator
def modinv1 (b, a, m): # return (b * a^{-1}) mod m --------------- fundamental EEA
    u, v = a, m
    x, y = b, 0
    while v != 0:
        q = u // v
        u, v = v, u - q * v
        x, y = y, x - q * y
    return x % m
def modinv2 (b, a, m): # return (b * a^{-1}) mod m -------------- removed division
    u, v = a, m
    x, y = b, 0
    while v != 0:
        q = 0 if u < v else 1
        u, v = v, u - q * v
        x, y = y, x - q * y
    return x % m
def modinv3 (b, a, m): # return (b * a^{-1}) mod m ------------ reduced iterations
    u, v = a, m
    x, y = b, 0
    while u != 1 and v != 1:
        if  u < v: v, y = v - u, y - x
        else:      u, x = u - v, x - y
    if  u == 1: return x % m
    else:       return y % m
def modinv4 (b, a, m): # return (b * a^{-1}) mod m ------ u/2, v/2, Algorithm 2.22
    u, v = a, m
    x, y = b, 0
    while u != 1 and v != 1:
        while u & 1 == 0:
            u = u                       // 2
            if  x & 1 == 0: x =  x      // 2
            else:           x = (x + m) // 2
        while v & 1 == 0:
            v = v                       // 2
            if  y & 1 == 0: y =  y      // 2
            else:           y = (y + m) // 2
        if  u < v: v, y = v - u, y - x
        else:      u, x = u - v, x - y
    if  u == 1: return x % m
    else:       return y % m
def modinv5 (b, a, m): # return (b * a^{-1}) mod m -------------- (u-v)/2, (v-u)/2
    u, v = a, m
    x, y = b, 0
    while u != 1 and v != 1:
        while u & 1 == 0:
            u = u                       // 2
            if  x & 1 == 0: x =  x      // 2
            else:           x = (x + m) // 2
        while v & 1 == 0:
            v = v                       // 2
            if  y & 1 == 0: y =  y      // 2
            else:           y = (y + m) // 2
        if  u < v:
            v, y = (v - u) // 2, y - x
            if  y & 1 == 0: y =  y      // 2
            else:           y = (y + m) // 2
        else:
            u, x = (u - v) // 2, x - y
            if  x & 1 == 0: x = x       // 2
            else:           x = (x + m) // 2
    if  u == 1: return x % m
    else:       return y % m
def modinv6 (b, a, m): # return (b * a^{-1}) mod m --- no u/2, no v/2, multiplexer
    u, v = a, m
    x, y = b, 0
    while u != 1 and v != 1:
        if u & 1 == 1: tv, ty = v, y
        else:          tv, ty = 0, 0
        if v & 1 == 1: tu, tx = u, x
        else:          tu, tx = 0, 0
        tuv, txy = tu - tv, tx - ty
        uv = tuv                        // 2
        if txy & 1 == 0: xy =  txy      // 2
        else:            xy = (txy + m) // 2
        if  uv < 0: v, y = -uv, -xy
        else:       u, x =  uv,  xy
    if  u == 1: return x % m
    else:       return y % m
def modinv7 (b, a, m): # return (b * a^{-1}) mod m ----------- negative assignment
    u, v = a, -m
    x, y = b, -0
    while u != 1:
        if u & 1 == 1: tv, ty = v, y
        else:          tv, ty = 0, 0
        if v & 1 == 1: tu, tx = u, x
        else:          tu, tx = 0, 0
        tuv, txy = tu + tv, tx + ty
        uv = tuv                        // 2
        if txy & 1 == 0: xy =  txy      // 2
        else:
            if txy < 0:  xy = (txy + m) // 2
            else:        xy = (txy - m) // 2
        if  uv < 0: v, y = uv, xy
        else:       u, x = uv, xy
    if  x < 0: x = x + m
    return x
def modinv_radix8 (b, a, m): # return (b * a^{-1}) mod m # proposed radix-8 modinv
    u, v = a, -m
    x, y = b, -0
    while u != 1:
        if u & 1 == 1: tv, ty = v, y
        else:          tv, ty = 0, 0
        if v & 1 == 1: tu, tx = u, x
        else:          tu, tx = 0, 0
        tuv, txy = tu + tv, tx + ty          # tuv is even
        if tuv & 6 == 0:                     # radix 8:
            uv = tuv                                            // 8
            if txy & 1 == 0:
                if txy & 2 == 0:
                    if txy & 4 == 0:         xy =  txy          // 8
                    else:                    xy = (txy + 4 * m) // 8
                else:
                    if txy & 4 == (m*2 & 4): xy = (txy - 2 * m) // 8
                    else:                    xy = (txy + 2 * m) // 8
            else:
                if txy & 6 == m & 6:         xy = (txy -     m) // 8
                else:
                    if txy & 2 == m & 2:     xy = (txy + 3 * m) // 8
                    else:
                        if txy & 4 != m & 4: xy = (txy +     m) // 8
                        else:                xy = (txy - 3 * m) // 8
        else:
            if tuv & 2 == 0:                 # radix 4:
                uv = tuv                                        // 4
                if txy & 1 == 0:
                    if txy & 2 == 0:         xy =  txy          // 4
                    else:                    xy = (txy + 2 * m) // 4
                else:
                    if txy & 3 == m & 3:     xy = (txy -     m) // 4
                    else:                    xy = (txy +     m) // 4
            else:                            # radix 2:
                uv = tuv                                        // 2
                if txy & 1 == 0:             xy =  txy          // 2
                else:
                    if txy < 0:              xy = (txy +     m) // 2
                    else:                    xy = (txy -     m) // 2
        if  uv < 0: v, y = uv, xy
        else:       u, x = uv, xy
    if  x < 0: x = x + m
    return x
m  = int (0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f)
b  = rand.getrandbits (256) % m
a  = rand.getrandbits (256) % m
c1 = modinv1 (b, a, m)
c2 = modinv2 (b, a, m)
c3 = modinv3 (b, a, m)
c4 = modinv4 (b, a, m)
c5 = modinv5 (b, a, m)
c6 = modinv6 (b, a, m)
c7 = modinv7 (b, a, m)
c  = modinv_radix8 (b, a, m)
print ('b  = 0x{:064x}'.format(b))
print ('a  = 0x{:064x}'.format(a))
print ('m  = 0x{:064x}'.format(m))
print ('c1 = 0x{:064x}'.format(c1))
print ('c2 = 0x{:064x}'.format(c2))
print ('c3 = 0x{:064x}'.format(c3))
print ('c4 = 0x{:064x}'.format(c4))
print ('c5 = 0x{:064x}'.format(c5))
print ('c6 = 0x{:064x}'.format(c6))
print ('c7 = 0x{:064x}'.format(c7))
print ('c  = 0x{:064x}'.format(c))
assert c1 == c2 == c3 == c4 == c5 == c6 == c7 == c
assert (c * a) % m == b # verify correctness