/*
Author: Shanji

Think twice, code once. 
*/
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
int char_to_int(char x) {
    return x >= '0' && x <= '9' ? x - '0' : 10 + x - 'A';
}
char int_to_char(int x) {
    return x >= 0 && x <= 9 ? x + '0' : x - 10 + 'A';
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    cin >> n >> s >> m;
    int num = char_to_int(s[0]);
    // for (int i = 0; i < s.size(); i++) {
    //  num += pow(n, s.size() - i - 1) * char_to_int(s[i]); // pow函数原来是有顺序要求的啊， 底数在前，指数在后。
    // }

// qinjiushao algorithm
    for (int i = 1; i < s.size(); i++) {
        num = num * n + char_to_int(s[i]);
    }
    // cout << num;
    string ans;
    while (1) {
        ans += int_to_char(num % m);
        num /= m;
        if (num < m) {
            ans += int_to_char(num);
            break;
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
    return 0;
}

1.学到了可以把一元多次多项式运算从O(n2)优化成O(n)的秦九韶关算法。
2.稍微证明了一下短除法的原理和正确性。
3.因为int的范围可以cover2.1 x 1e9所以不用开long long。（题目数据范围1e9即十亿）