#!/usr/bin/python
import math

def isPrime(n):
    for i in range(2,math.floor(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def nthPrime(n):
    i=0
    j=1
    while i != n:
        j=j+1
        if isPrime(j) == True:
            i=i+1
    return j


def gcd(a,q):
    r=a%q
    if r == 0:
        return q
    else:
        return gcd(q,r)

def phi(n):
    ans=0
    for i in range(n):
        if gcd(i,n) == 1:
            ans=ans+1
    return ans




def encrypt(n,e,mes):
    resp = 1
    for i in range(0,math.floor(math.log2(e))+1):
        if e%2 != 0:
            resp = (resp*(mes**(2**i)))%n
        e=math.floor(e/2)
    return resp


def decrypt(n,d,cif):
    resp = 1
    for i in range(0,math.floor(math.log2(d))+1):
        if d%2 != 0:
            resp = (resp*(cif**(2**i)))%n
        d=math.floor(d/2)

    return resp

def encode(s):
    l = []
    ltn = {
    "A" : 0,
    "B" : 1,
    "C" : 2,
    "D" : 3,
    "E" : 4,
    "F" : 5,
    "G" : 6,
    "H" : 7,
    "I" : 8,
    "J" : 9,
    "K" : 10,
    "L" : 11,
    "M" : 12,
    "N" : 13,
    "O" : 14,
    "P" : 15,
    "Q" : 16,
    "R" : 17,
    "S" : 18,
    "T" : 19,
    "U" : 20,
    "V" : 21,
    "W" : 22,
    "X" : 23,
    "Y" : 24,
    "Z" : 25,
    }
    for c in s:
        l.append(encrypt(9480469,65537,ltn[c]))
    return l

def decode(l):
    s = ""
    ntl = {
    "0" : "A",
    "1" : "B",
    "2" : "C",
    "3" : "D",
    "4" : "E",
    "5" : "F",
    "6" : "G",
    "7" : "H",
    "8" : "I",
    "9" : "J",
    "10" : "K",
    "11" : "L",
    "12" : "M",
    "13" : "N",
    "14" : "O",
    "15" : "P",
    "16" : "Q",
    "17" : "R",
    "18" : "S",
    "19" : "T",
    "20" : "U",
    "21" : "V",
    "22" : "W",
    "23" : "X",
    "24" : "Y",
    "25" : "Z",
    }


    for i in l:
        s=s+ntl[str(decrypt(9480469,604273,i))]
    return s