from math import log2, ceil
from random import randint


def fast_pow(a, x, p):
    t = ceil(log2(x))
    x = list(bin(x))[2:]
    y = 1
    s = a
    x.reverse()
    for i in range(t):
        if int(x[i]) == 1:
            y = y * s % p
        s = s * s % p
    return y

def extended_gcd(a, b):
    u = [a, 1, 0]
    v = [b, 0, 1]
    while v[0] != 0:
        q = u[0] // v[0]
        t = [u[0] % v[0], u[1] - q * v[1], u[2] - q * v[2]]
        u = v
        v = t
    return u

def g_generate(p):
    g = 2
    q = (p - 1) // 2
    while(g > 1 and (g < p - 1) and fast_pow(q, g, p) != 1):
        g += 1
    return g

def diffie_hellman(p):
    g = randint(1, p - 1)
    Xa = randint(1, 1000)
    Xb = randint(1, 1000)
    Ya = fast_pow(g, Xa, p)
    Yb = fast_pow(g, Xb, p)
    Ka = fast_pow(Yb, Xa, p)
    Kb = fast_pow(Ya, Xb, p)
    return (Ka, Kb)


print("ans=", fast_pow(17, 984, 31))

# print(extended_gcd(28, 19))

# print(diffie_hellman(9973))