# Fast modulo exponentiation of numbers using Euler
# Rafał Lal 10/06/2021
import sys
from sympy.ntheory import isprime
from math import gcd


def euler_function(num):
    if isprime(num):
        return num - 1
    result = 1
    for i in range(2, num):
        if gcd(i, num) == 1:
            result += 1
    return result


def euler_theorem(a, n, m):
    eul = euler_function(m)
    n1 = n % eul
    n2 = pow(a, n1)
    return eul, n2 % m


def main():
    try:
        a = int(input('Base: '))
        n = int(input('Power: '))
        m = int(input('Mod: '))
        if n < 1 or m < 1 or gcd(a, m) != 1:
            raise ValueError
    except ValueError:
        print('Numbers does not fulfil requirements')
        sys.exit()

    e, r = euler_theorem(a, n, m)
    print('Euler({}) = {}'.format(m, e), "Result = {} <{}>".format(r, m), sep='\n')


if __name__ == '__main__':
    main()
