# Arup Guha
# Solution to CIS 3362 Homework #5 Question 9
# 11/8/2019

# Given values
n = 135966249934813212187094231381
e = 437623485647823657465674567

# Fast modular exponentiation
def modpow(b,exp,mod):

    # Base case.
    if exp == 0:
        return 1

    # Time savings here, go halfway and square.
    if exp%2 == 0:
        tmp = modpow(b,exp//2,mod)
        return (tmp*tmp)%mod

    # Usual breakdown.
    return (modpow(b,exp-1,n)*b)%mod


# Converts s (assumed to be in Radix-64) to the corresponding int value.
def convert(s):

    val = 0

    # Use Horner's Method - shift value by 2**6 each time and add next char.
    for i in range(len(s)):
        val = 64*val + code(s[i])

    # Ta da
    return val

# Returns the Radix-64 code for c, assuming it's a valid Radix-64 character.
def code(c):

    # Upper case letters are 0 to 25.
    if c >= 'A' and c <= 'Z':
        return ord(c) - ord('A')

    # Lower case are 26 to 51.
    elif c >= 'a' and c <= 'z':
        return ord(c) - ord('a') + 26

    # Digits are 52 to 61.
    elif c >= '0' and c <= '9':
        return ord(c) - ord('0') + 52

    # These 2 are special!
    elif c == '+':
        return 62
    return 63

def main():
    
    # Read in the whole file.
    file = open("msg.txt", "r")
    toks = file.read().split()

    # Encrypt each token and output to standard output.
    for i in range(len(toks)):

        msg = convert(toks[i])
        print(modpow(msg,e, n))

    file.close()

main()