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