#include <stdio.h>
#include <string.h>
#include <vector>
#define maxd 10000000
using namespace std;
const int mod = 998244353;
typedef long long ll;
ll rd()
{
ll k = 0;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + (c ^ 48);
c = getchar();
}
return k;
}
void wr(ll x)
{
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
void swap(int *a, int *b)
{
if ((*a) != (*b))
(*a) ^= (*b), (*b) ^= (*a), (*a) ^= (*b);
}
int _inv(int a)
{
int _a = a, _b = mod, u = 1, v = 0;
while (_b)
{
int t = _a / _b;
_a -= t * _b;
swap(&_a, &_b);
u -= t * v;
swap(&u, &v);
}
u += mod, u %= mod;
return u;
}
int quick_pow(int x, ll p)
{
ll ans = 1;
while (p)
{
if (p & 1)
ans = ans * x % mod;
x = 1ll * x * x % mod;
p >>= 1;
}
return ans;
}
int inv[maxd + 10], cur_max_d;
int s1[maxd + 10], s2[maxd + 10];
void init_all() { inv[1] = 1, cur_max_d = 1; }
void init_inv(int d)
{
if (cur_max_d < d)
for (int i = cur_max_d + 1; i <= d + 1; ++i)
inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
cur_max_d = d;
}
void init_case_1(int d) { memset(s1, 0, sizeof(s1[0]) * (d + 1)); }
void init_case_2(int d) { memset(s1, 0, sizeof(s1[0]) * (d + 1)), memset(s2, 0, sizeof(s2[0]) * (d + 1)); }
void debug_print_status(int d)
{
puts("current s : ");
for (int i = 0; i <= d; ++i)
wr(s1[i]), putchar(i == d ? '\n' : ' ');
}
// \sum_{i=0}^{n-1} {(r^i)*(i^d)}
int sum_of_exp_time_poly(int r, int d, char *n)
{
init_inv(d);
int ans = 0;
int len = strlen(n);
ll mod_n = 0, pow_n = 0;
if (len < 20)
{
for (int i = 0; i < len; ++i)
mod_n = (mod_n << 1) + (mod_n << 3) + (n[i] ^ '0');
pow_n = mod_n % (mod - 1), mod_n %= mod;
}
else
{
for (int i = 0; i < len; ++i)
{
mod_n = (mod_n << 1) + (mod_n << 3) + (n[i] ^ '0');
pow_n = (pow_n << 1) + (pow_n << 3) + (n[i] ^ '0');
mod_n = (mod_n >= mod) ? mod_n % mod : mod_n;
pow_n = (pow_n >= (mod - 1)) ? pow_n % (mod - 1) : pow_n;
}
}
if (r == 1)
{
/*
init_case_1(d);
for (int i = 0, t = 0, b = 1; i <= d; ++i)
{
b = 1ll * b * (mod_n + mod - i) % mod * inv[i + 1] % mod;
t = (t + quick_pow(i, d)) % mod;
s1[i] = 1ll * t * b % mod;
}
debug_print_status(d);
for (int i = 0, b = 1; i <= d; ++i)
{
ans = (ans + 1ll * b * ((i & 1) ? mod - s1[d - i] : s1[d - i])) % mod;
b = 1ll * b * (mod_n + mod - 1 - (d - i)) % mod * inv[i + 1] % mod;
}
*/
vector<int> s(d + 1);
for (int i = 0, t = 0, b = 1; i <= d; ++i)
{
b = 1ll * b * (mod_n + mod - i) % mod * inv[i + 1] % mod;
t = (t + quick_pow(i, d)) % mod;
s[i] = 1ll * t * b % mod;
}
for (int i = 0, b = 1; i <= d; ++i)
{
ans = (ans + 1ll * b * ((i & 1) ? mod - s[d - i] : s[d - i])) % mod;
b = 1ll * b * (mod_n + mod - 1 - (d - i)) % mod * inv[i + 1] % mod;
}
}
else
{
init_case_2(d);
int t1 = 0, t2 = 0;
for (int i = 0, rpow = 1; i <= d; ++i, rpow = 1ll * rpow * r % mod)
{
s1[i] = t1 = (t1 + 1ll * quick_pow(i, d) * rpow) % mod;
s2[i] = t2 = (t2 + 1ll * quick_pow(i + mod_n, d) * rpow) % mod;
}
int ans1 = 0, ans2 = 0, b = 1, mr = mod - r;
for (int i = 0; i <= d; ++i)
{
ans1 = (ans1 + 1ll * b * s1[d - i]) % mod;
ans2 = (ans2 + 1ll * b * s2[d - i]) % mod;
b = 1ll * b * mr % mod * (d + 1 - i) % mod * inv[i + 1] % mod;
}
ans = ans1 + mod - 1ll * quick_pow(r, pow_n) * ans2 % mod;
ans = 1ll * ans * _inv(quick_pow(mod + 1 - r, d + 1)) % mod;
}
return ans;
}
int sum_of_exp_time_poly_limit(int r, int d)
{
init_inv(d);
init_case_1(d);
int t = 0;
for (int i = 0; i <= d; ++i)
t = (t + 1ll * quick_pow(i, d) * quick_pow(r, i)) % mod, s1[i] = t;
int ans = 0, b = 1, mr = mod - r;
for (int i = 0; i <= d; ++i)
{
ans = (ans + 1ll * b * s1[d - i]) % mod;
b = 1ll * b * mr % mod * (d + 1 - i) % mod * inv[i + 1] % mod;
}
ans = 1ll * ans * _inv(quick_pow(mod + 1 - r, d + 1)) % mod;
return ans;
}
int r, d;
char n[100010];
int main()
{
init_all();
// while (~scanf("%d%d", &r, &d))
// printf("%d\n", sum_of_exp_time_poly_limit(r, d));
while (~scanf("%d%d%s", &r, &d, n))
printf("%d\n", sum_of_exp_time_poly(r, d, n));
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2RlZmluZSBtYXhkIDEwMDAwMDAwCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBtb2QgPSA5OTgyNDQzNTM7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwpsbCByZCgpCnsKICAgIGxsIGsgPSAwOwogICAgY2hhciBjID0gZ2V0Y2hhcigpOwogICAgd2hpbGUgKGMgPCAnMCcgfHwgYyA+ICc5JykKICAgICAgICBjID0gZ2V0Y2hhcigpOwogICAgd2hpbGUgKGMgPj0gJzAnICYmIGMgPD0gJzknKQogICAgewogICAgICAgIGsgPSAoayA8PCAxKSArIChrIDw8IDMpICsgKGMgXiA0OCk7CiAgICAgICAgYyA9IGdldGNoYXIoKTsKICAgIH0KICAgIHJldHVybiBrOwp9CnZvaWQgd3IobGwgeCkKewogICAgaWYgKHggPiA5KQogICAgICAgIHdyKHggLyAxMCk7CiAgICBwdXRjaGFyKHggJSAxMCArICcwJyk7Cn0Kdm9pZCBzd2FwKGludCAqYSwgaW50ICpiKQp7CiAgICBpZiAoKCphKSAhPSAoKmIpKQogICAgICAgICgqYSkgXj0gKCpiKSwgKCpiKSBePSAoKmEpLCAoKmEpIF49ICgqYik7Cn0KCmludCBfaW52KGludCBhKQp7CiAgICBpbnQgX2EgPSBhLCBfYiA9IG1vZCwgdSA9IDEsIHYgPSAwOwogICAgd2hpbGUgKF9iKQogICAgewogICAgICAgIGludCB0ID0gX2EgLyBfYjsKICAgICAgICBfYSAtPSB0ICogX2I7CiAgICAgICAgc3dhcCgmX2EsICZfYik7CiAgICAgICAgdSAtPSB0ICogdjsKICAgICAgICBzd2FwKCZ1LCAmdik7CiAgICB9CiAgICB1ICs9IG1vZCwgdSAlPSBtb2Q7CiAgICByZXR1cm4gdTsKfQoKaW50IHF1aWNrX3BvdyhpbnQgeCwgbGwgcCkKewogICAgbGwgYW5zID0gMTsKICAgIHdoaWxlIChwKQogICAgewogICAgICAgIGlmIChwICYgMSkKICAgICAgICAgICAgYW5zID0gYW5zICogeCAlIG1vZDsKICAgICAgICB4ID0gMWxsICogeCAqIHggJSBtb2Q7CiAgICAgICAgcCA+Pj0gMTsKICAgIH0KICAgIHJldHVybiBhbnM7Cn0KCmludCBpbnZbbWF4ZCArIDEwXSwgY3VyX21heF9kOwppbnQgczFbbWF4ZCArIDEwXSwgczJbbWF4ZCArIDEwXTsKCnZvaWQgaW5pdF9hbGwoKSB7IGludlsxXSA9IDEsIGN1cl9tYXhfZCA9IDE7IH0Kdm9pZCBpbml0X2ludihpbnQgZCkKewogICAgaWYgKGN1cl9tYXhfZCA8IGQpCiAgICAgICAgZm9yIChpbnQgaSA9IGN1cl9tYXhfZCArIDE7IGkgPD0gZCArIDE7ICsraSkKICAgICAgICAgICAgaW52W2ldID0gMWxsICogaW52W21vZCAlIGldICogKG1vZCAtIG1vZCAvIGkpICUgbW9kOwogICAgY3VyX21heF9kID0gZDsKfQp2b2lkIGluaXRfY2FzZV8xKGludCBkKSB7IG1lbXNldChzMSwgMCwgc2l6ZW9mKHMxWzBdKSAqIChkICsgMSkpOyB9CnZvaWQgaW5pdF9jYXNlXzIoaW50IGQpIHsgbWVtc2V0KHMxLCAwLCBzaXplb2YoczFbMF0pICogKGQgKyAxKSksIG1lbXNldChzMiwgMCwgc2l6ZW9mKHMyWzBdKSAqIChkICsgMSkpOyB9CnZvaWQgZGVidWdfcHJpbnRfc3RhdHVzKGludCBkKQp7CiAgICBwdXRzKCJjdXJyZW50IHMgOiAiKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IGQ7ICsraSkKICAgICAgICB3cihzMVtpXSksIHB1dGNoYXIoaSA9PSBkID8gJ1xuJyA6ICcgJyk7Cn0KLy8gXHN1bV97aT0wfV57bi0xfSB7KHJeaSkqKGleZCl9CmludCBzdW1fb2ZfZXhwX3RpbWVfcG9seShpbnQgciwgaW50IGQsIGNoYXIgKm4pCnsKICAgIGluaXRfaW52KGQpOwogICAgaW50IGFucyA9IDA7CiAgICBpbnQgbGVuID0gc3RybGVuKG4pOwogICAgbGwgbW9kX24gPSAwLCBwb3dfbiA9IDA7CiAgICBpZiAobGVuIDwgMjApCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBsZW47ICsraSkKICAgICAgICAgICAgbW9kX24gPSAobW9kX24gPDwgMSkgKyAobW9kX24gPDwgMykgKyAobltpXSBeICcwJyk7CiAgICAgICAgcG93X24gPSBtb2RfbiAlIChtb2QgLSAxKSwgbW9kX24gJT0gbW9kOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbGVuOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBtb2RfbiA9IChtb2RfbiA8PCAxKSArIChtb2RfbiA8PCAzKSArIChuW2ldIF4gJzAnKTsKICAgICAgICAgICAgcG93X24gPSAocG93X24gPDwgMSkgKyAocG93X24gPDwgMykgKyAobltpXSBeICcwJyk7CiAgICAgICAgICAgIG1vZF9uID0gKG1vZF9uID49IG1vZCkgPyBtb2RfbiAlIG1vZCA6IG1vZF9uOwogICAgICAgICAgICBwb3dfbiA9IChwb3dfbiA+PSAobW9kIC0gMSkpID8gcG93X24gJSAobW9kIC0gMSkgOiBwb3dfbjsKICAgICAgICB9CiAgICB9CiAgICBpZiAociA9PSAxKQogICAgewogICAgICAgIC8qCiAgICAgICAgaW5pdF9jYXNlXzEoZCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDAsIHQgPSAwLCBiID0gMTsgaSA8PSBkOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBiID0gMWxsICogYiAqIChtb2RfbiArIG1vZCAtIGkpICUgbW9kICogaW52W2kgKyAxXSAlIG1vZDsKICAgICAgICAgICAgdCA9ICh0ICsgcXVpY2tfcG93KGksIGQpKSAlIG1vZDsKICAgICAgICAgICAgczFbaV0gPSAxbGwgKiB0ICogYiAlIG1vZDsKICAgICAgICB9CiAgICAgICAgZGVidWdfcHJpbnRfc3RhdHVzKGQpOwogICAgICAgIGZvciAoaW50IGkgPSAwLCBiID0gMTsgaSA8PSBkOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBhbnMgPSAoYW5zICsgMWxsICogYiAqICgoaSAmIDEpID8gbW9kIC0gczFbZCAtIGldIDogczFbZCAtIGldKSkgJSBtb2Q7CiAgICAgICAgICAgIGIgPSAxbGwgKiBiICogKG1vZF9uICsgbW9kIC0gMSAtIChkIC0gaSkpICUgbW9kICogaW52W2kgKyAxXSAlIG1vZDsKICAgICAgICB9CiAgICAgICAgKi8KICAgICAgICB2ZWN0b3I8aW50PiBzKGQgKyAxKTsKICAgICAgICBmb3IgKGludCBpID0gMCwgdCA9IDAsIGIgPSAxOyBpIDw9IGQ7ICsraSkKICAgICAgICB7CiAgICAgICAgICAgIGIgPSAxbGwgKiBiICogKG1vZF9uICsgbW9kIC0gaSkgJSBtb2QgKiBpbnZbaSArIDFdICUgbW9kOwogICAgICAgICAgICB0ID0gKHQgKyBxdWlja19wb3coaSwgZCkpICUgbW9kOwogICAgICAgICAgICBzW2ldID0gMWxsICogdCAqIGIgJSBtb2Q7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAwLCBiID0gMTsgaSA8PSBkOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBhbnMgPSAoYW5zICsgMWxsICogYiAqICgoaSAmIDEpID8gbW9kIC0gc1tkIC0gaV0gOiBzW2QgLSBpXSkpICUgbW9kOwogICAgICAgICAgICBiID0gMWxsICogYiAqIChtb2RfbiArIG1vZCAtIDEgLSAoZCAtIGkpKSAlIG1vZCAqIGludltpICsgMV0gJSBtb2Q7CiAgICAgICAgfQogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGluaXRfY2FzZV8yKGQpOwogICAgICAgIGludCB0MSA9IDAsIHQyID0gMDsKICAgICAgICBmb3IgKGludCBpID0gMCwgcnBvdyA9IDE7IGkgPD0gZDsgKytpLCBycG93ID0gMWxsICogcnBvdyAqIHIgJSBtb2QpCiAgICAgICAgewogICAgICAgICAgICBzMVtpXSA9IHQxID0gKHQxICsgMWxsICogcXVpY2tfcG93KGksIGQpICogcnBvdykgJSBtb2Q7CiAgICAgICAgICAgIHMyW2ldID0gdDIgPSAodDIgKyAxbGwgKiBxdWlja19wb3coaSArIG1vZF9uLCBkKSAqIHJwb3cpICUgbW9kOwogICAgICAgIH0KICAgICAgICBpbnQgYW5zMSA9IDAsIGFuczIgPSAwLCBiID0gMSwgbXIgPSBtb2QgLSByOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IGQ7ICsraSkKICAgICAgICB7CiAgICAgICAgICAgIGFuczEgPSAoYW5zMSArIDFsbCAqIGIgKiBzMVtkIC0gaV0pICUgbW9kOwogICAgICAgICAgICBhbnMyID0gKGFuczIgKyAxbGwgKiBiICogczJbZCAtIGldKSAlIG1vZDsKICAgICAgICAgICAgYiA9IDFsbCAqIGIgKiBtciAlIG1vZCAqIChkICsgMSAtIGkpICUgbW9kICogaW52W2kgKyAxXSAlIG1vZDsKICAgICAgICB9CiAgICAgICAgYW5zID0gYW5zMSArIG1vZCAtIDFsbCAqIHF1aWNrX3BvdyhyLCBwb3dfbikgKiBhbnMyICUgbW9kOwogICAgICAgIGFucyA9IDFsbCAqIGFucyAqIF9pbnYocXVpY2tfcG93KG1vZCArIDEgLSByLCBkICsgMSkpICUgbW9kOwogICAgfQogICAgcmV0dXJuIGFuczsKfQppbnQgc3VtX29mX2V4cF90aW1lX3BvbHlfbGltaXQoaW50IHIsIGludCBkKQp7CiAgICBpbml0X2ludihkKTsKICAgIGluaXRfY2FzZV8xKGQpOwogICAgaW50IHQgPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPD0gZDsgKytpKQogICAgICAgIHQgPSAodCArIDFsbCAqIHF1aWNrX3BvdyhpLCBkKSAqIHF1aWNrX3BvdyhyLCBpKSkgJSBtb2QsIHMxW2ldID0gdDsKCiAgICBpbnQgYW5zID0gMCwgYiA9IDEsIG1yID0gbW9kIC0gcjsKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IGQ7ICsraSkKICAgIHsKICAgICAgICBhbnMgPSAoYW5zICsgMWxsICogYiAqIHMxW2QgLSBpXSkgJSBtb2Q7CiAgICAgICAgYiA9IDFsbCAqIGIgKiBtciAlIG1vZCAqIChkICsgMSAtIGkpICUgbW9kICogaW52W2kgKyAxXSAlIG1vZDsKICAgIH0KICAgIGFucyA9IDFsbCAqIGFucyAqIF9pbnYocXVpY2tfcG93KG1vZCArIDEgLSByLCBkICsgMSkpICUgbW9kOwogICAgcmV0dXJuIGFuczsKfQppbnQgciwgZDsKY2hhciBuWzEwMDAxMF07CmludCBtYWluKCkKewogICAgaW5pdF9hbGwoKTsKICAgIC8vIHdoaWxlICh+c2NhbmYoIiVkJWQiLCAmciwgJmQpKQogICAgICAgIC8vIHByaW50ZigiJWRcbiIsIHN1bV9vZl9leHBfdGltZV9wb2x5X2xpbWl0KHIsIGQpKTsKICAgIHdoaWxlICh+c2NhbmYoIiVkJWQlcyIsICZyLCAmZCwgbikpCiAgICAgICAgcHJpbnRmKCIlZFxuIiwgc3VtX29mX2V4cF90aW1lX3BvbHkociwgZCwgbikpOwp9Cg==