//土尔逊Torson 编写于2023/5/06
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

char IntToChar06501(int x) {      //数字转字符
	if (x < 10) {
		return x + '0';
	}
	else {
		return x - 10 + 'a';
	}
}

int CharToInt06501(char c) {      //字符转数字
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	else{
		return c - 'A' + 10;
	}
}

int getpos(string str) {           //获取空格位置
	int pos;
	for (unsigned int i = 0; i < str.size(); ++i) {
		if (str[i] == ' ') {
			pos = i;
			break;
		}
	}
	return pos;
}

string upper(string str) {         //转换成大写字母
	for (unsigned int i = 0; i < str.size(); ++i) {
		if (str[i] >= 'a'&& str[i] <= 'f') {
			str[i] = str[i] - 32;
		}
	}
	return str;
}

int main() {
	int m, n;
	string str;
	while (getline(cin, str)) {
		int pos = getpos(str);      //全部字母转换成大写字母
		str = upper(str);
		string aS, bS;              //从字符串截取 题意输入的数字 a 和 b,并保留 N 字符串
		aS = str.substr(0, pos);
		str = str.substr(pos + 1);
		pos = getpos(str);
		bS = str.substr(pos + 1);
		str = str.substr(0, pos);

		m = stoi(aS);
		n = stoi(bS);

		long long number = 0;
		for (int i = 0; i < str.size(); ++i) {        //m进制转十进制
			number *= m;
			number += CharToInt06501(str[i]);
		}
		vector<char> answer;
		while (number != 0) {                         //十进制转n进制
			answer.push_back(IntToChar06501(number % n));
			number /= n;
		}
		for (int i = answer.size() - 1; i >= 0; --i) { //逆序输出
			if (answer[i] >= 'a'&& answer[i] <= 'f') { //结果全部转换成大写输出
				answer[i] = answer[i] - 32;
			}
			printf("%c", answer[i]);
		}
		printf("\n");
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")