ASFDASFDA

import random

p = 2147

def powMod(x, a):
    y = 1
    while(a!=0):
        y = y * x
        if(len(str(y%(10**len(str(p))))) > len(str(p))):
            y = y % (10**len(str(p)))
        a = a - 1
    return y%p

def inversePowMod(a, p):
    for i in range(p):
        if a*i % p == 1:
            return i
    return - 1

#print(powMod(1407, 2301))
#print(inversePowMod(2301,2147))


def factorizare(x):
    lista = []
    if(x == 0):
        print("nu are factori")
    elif(x == 1):
        lista.append(1, 1)
    else:
        i = 2
        while(i <= x):
            k = 0
            while(x%i==0):
                x = x/i
                k = k + 1
            if k != 0:
                lista.append([i, k])
            i = i + 1
    if (lista != []):
        print("[factor, putere]")
        for y in lista:
            print(y)

def isPrime(n, k):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True

    d = n - 1
    while(d % 2 == 0):
        d = d//2
    for i in range(k):
        if(millerTest(d, n) == False):
            return False

    return True

def millerTest(d, n):
    a = 2 + random.randint(1, n-4)

    x = power(a, d, n);

    if (x == 1 or x == n - 1):
        return True

    while(d != n - 1):
        x = (x*x)%n
        d=d*2

        if x == 1:
            return False
        if x == n - 1:
            return True
    return False

def power(x, y, p):
    res = 1

    x = x % p
    while(y>0):
        if y & 1:
            res = res * x % p

        y = y >> 1
        x = x * x % p
    return res

#print(isPrime(1000000016531, 4))

def cmmdc(n , m):
    if m > n:
        x = m
        m = n
        n = x
    while (m != 0):
        r = n % m
        n = m
        m = r
        return n

#print(cmmdc(555,15))



def RSA():