#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

int n;

void write(int n) {
    string ans;
    while (n) {
        int d = n % 16;
        if (d < 10) ans.push_back((char)(d + '0'));
        else ans.push_back((char)(d - 10 + 'a'));
        n /= 16;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

int read(const string& s) {
    int res = 0;
    for (auto& i : s) {
        res *= 16;
        if (i >= '0' && i <= '9') res += (int)i - '0';
        else res += (int)i - 'a' + 10;
    }
    return res;
}

void solve() {
    vector<int> d;
    for (int k = 2; k * k <= n; ++k) {
        if (n % k == 0) {
            n /= k;
            d.push_back(k);
        }
    }
    if (n > 1) d.push_back(n);
    for (auto& i : d) write(i);
    exit(0);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cout << fixed << setprecision(20);
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int b, k;
    string s;
    cin >> b >> k;
    cin >> s;
    n = read(s);

    if (k == 4) solve();

    vector<int> d;
    if (n % 2 == 0) {
        d.push_back(2);
        n /= 2;
    }

    int st = max((int)(sqrt(n) - 1e6), 3LL);
    if (st % 2 == 0) --st;
    for (int k = st; k <= (int)(sqrt(n) + 1e6); k += 2) {
        if (n % k == 0) {
            d.push_back(k);
            n /= k;
        }
        if (n == 1) break;
    }
    if (n > 1) d.push_back(n);

    for (auto& i : d) write(i);
}