#!/usr/bin/env python
# -*- coding: utf-8 -*-

#import psyco

def s2n(s):
    return long(s, 16)

def n2s(num):
    if num < 0:
        num *= -1
    s = ''
    while 1:
        s = chr(num % 256) + s
        num = num // 256
        if num == 0:
            break
    return s


def egcd(a, b):
    """Extended Euclid's algorithm for GCD.
    Given input a, b the function returns d such that gcd(a,b) = d
    and x, y such that ax + by = d, as well as u, v such that au = bv."""
#    if a < b:
#        a, b = b, a
    u, v, x, y = 0, 1, 1, 0
    while b != 0:
        a, b, x, y, u, v = b, a % b, u, v, x - ( a // b ) * u, y - ( a // b ) * v
    return a, x, y, u, v

def gcd(a, b):
  """Compute GCD of two numbers"""
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    if x < 0:
        x *= -1
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

def derive_p(e, nc):
    """Figure out RSA plaintext from a set of encrypted messages"""
    m = 1
    x = 0
    for i in xrange(0, len(nc)):
        m *= nc[i][0]
    for i in xrange(0, len(nc)):
        mi = nc[i][0]
        ai = nc[i][1]
        g = egcd(m/mi, mi)
        ri = g[2]
        si = g[1]
#        ei = 1-(ri*mi)
        ei = si*(m/mi)
        x += ai*ei
    x = x % m
    return find_invpow(x, e)

if __name__ == '__main__':
    psyco.full()
    data = {}

    fd = open('prrr')
    item = fd.readline()
    while item:
        if item.find('To') == 0:
            mm = item.rstrip().replace('To (', '').replace('):', '').replace(' ', '').split(',')
            n = s2n(mm[0])
            e = long(mm[1])
            c = fd.readline()
            if not data.get(e):
                data[e] = []
            data[e].append({ 0 : n, 1 : s2n(c.rstrip())})
        item = fd.readline()
    fd.close()
    for k,v in data.iteritems():
        print n2s(derive_p(k, v))