list1=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
while True:
    try:
        M,N=map(int,input().strip().split())
        num=input()
        list=[]
        sum=0
        for i in range(len(num)):
            if '0' <= num[i] <= '9': sum+=M**(len(num)-i-1)*(int(num[i]))
            else: sum+=M**(len(num)-i-1)*(list1.index(num[i])+10)
        while sum>0:
            list.append(sum % N)
            sum //= N
        list.reverse()
        for i in range(len(list)):
            if 0 <= list[i] <= 9:
                print(list[i], end='')
            else:
                print(list1[list[i] + 10], end='')
        print()

    except EOFError:
        break