#include <bits/stdc++.h>
#define N 133333
#define K 254
#define lg2(x) (31 - __builtin_clz(x))

typedef int vec[N], *pvec;
typedef long long ll;
const ll mod = 998244353, half_mod = (mod + 1) / 2, root = 31;
const char output[30] = "0123456789ABCDEFGHIJKLMNOPQRS";

vec fact, finv, ln;

ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

namespace Poly {
	int l, n; vec rev, x, y;

	void NTT_init(int len) {
		if (l == len) return; n = 1 << (l = len);
		ll g = PowerMod(root, 1 << (23 - l));
		*x = 1, *rev = 0;
		for (int i = 1; i < n; ++i) x[i] = x[i - 1] * g % mod, rev[i] = rev[i >> 1] >> 1 | (i & 1) << (l - 1);
	}

	void DNTT(int *d, int *t) {
		int i, *j, *k, len = 1, delta = n, R;
		for (i = 0; i < n; ++i) t[rev[i]] = d[i];
		for (i = 0; i < l; ++i) {
			delta >>= 1;
			for (k = x, j = y; j < y + len; k += delta, ++j) *j = *k;
			for (j = t; j < t + n; j += len << 1)
				for (k = j; k < j + len; ++k) {
					R = (ll)y[k - j] * k[len] % mod;
					k[len] = (*k - R < 0 ? *k - R + mod : *k - R);
					*k = (*k + R >= mod ? *k + R - mod : *k + R);
				}
			len <<= 1;
		}
	}

	vec B1;

	void Mul(int deg, pvec a, pvec b, pvec c) {
		if (!deg) {*c = (ll)*a * *b % mod; return;}
		NTT_init(lg2(deg) + 1);
		int i; ll iv = PowerMod(n, mod - 2);
		DNTT(a, c); DNTT(b, B1);
		for (i = 0; i < n; ++i) B1[i] = (ll)B1[i] * c[i] % mod;
		DNTT(B1, c); std::reverse(c + 1, c + n);
		for (i = 0; i < n; ++i) c[i] = c[i] * iv % mod;
	}
}

char n[K];
int p, g, ALL = 0;
int len = 0, dn[K];
vec f, fc, fr, ans;

void init() {
	int i; ll c;
	for (*fact = i = 1; i < p; ++i) fact[i] = (ll)fact[i - 1] * i % p;
	for (--i, finv[i] = i; i; --i) finv[i - 1] = (ll)finv[i] * i % p;
	for (g = 0; i != p - 1; )
		for (i = 1, c = ++g; c != 1; ++i, c = c * g % p);
	for (i = 0, c = 1; i != p - 1; ++i, c = c * g % p) ln[c] = i;
}

int C(int n, int r) {return n < r ? 0 : (ll)fact[n] * finv[r] % p * finv[n - r] % p;}

void solve() {
	int i, j, ind;
	memset(f, 0, p << 2), *f = 1;
	for (j = 0; j < len; ++j) {
		memset(fc, 0, p << 3);
		for (i = 0; i <= dn[j]; ++i) ++fc[ ind = ln[C(dn[j], i)] ];
		Poly::Mul(2 * (p - 1), f, fc, fr);
		for (i = 0; i < p - 1; ++i) f[i] = (fr[i] + fr[i + p - 1]) % 29;
	}
	for (i = 1; i < p; ++i) ALL -= ans[i] = f[ln[i]];
	++ALL %= 29, *ans = ALL + (ALL >> 31 & 29);
}

void decomposition(const char *s, int *ret) {
	int i, n = strlen(s), a[K];
	for (i = 0; i < n; ++i) a[n - i - 1] = s[i] & 15, ALL = (ALL * 10 + a[n - i - 1]) % 29;
	for (; ; ) {
		for (i = n - 1; i; --i) a[i - 1] += a[i] % p * 10, a[i] /= p;
		for (; n && !a[n - 1]; --n);
		if (n) ret[len++] = a[0] % p, a[0] /= p;
		else return;
	}
}

int main() {
	scanf("%s%d", n, &p), init(), decomposition(n, dn), solve();
	for (int i = 0; i < p; ++i) putchar(output[ans[i]]);
	return putchar(10), 0;
}