///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1 << 20, M = N * 2;
const int mod = 998244353, g = 3;
int fact[N], inv[N];
inline int Pow(int a, int p) {
int ret = 1; while(p) {
if(p & 1) ret = (ll) ret * a % mod;
a = (ll) a * a % mod;
p >>= 1;
} return ret;
}
inline void precalc() {
fact[0] = 1;
for(int i = 1; i < N; ++i) {
fact[i] = (ll) fact[i - 1] * i % mod;
}
inv[N - 1] = Pow(fact[N - 1], mod - 2);
for(int i = N - 2; i >= 0; --i) {
inv[i] = (ll) inv[i + 1] * (i + 1) % mod;
}
}
int rev[M], w[M], inv_n;
inline void prepare(int &n) {
int sz = 31 - __builtin_clz(n); sz = abs(sz);
int r = Pow(g, (mod - 1) / n);
inv_n = Pow(n, mod - 2);
w[0] = w[n] = 1;
for(int i = 1; i < n; ++i) w[i] = (ll)w[i - 1] * r % mod;
for(int i = 1; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (sz - 1));
}
inline void ntt(int *a, int n, int dir = 0) {
for(int i = 1; i < n - 1; ++i)
if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int m = 2; m <= n; m <<= 1) {
for(int i = 0; i < n; i += m) {
for(int j = 0; j < (m >> 1); ++j) {
int &u = a[i + j], &v = a[i + j + (m >> 1)];
int t = (ll)v * w[dir ? n - n / m * j : n / m * j] % mod;
v = u - t < 0 ? u - t + mod : u - t;
u = u + t >= mod ? u + t - mod : u + t;
}
}
} if(dir) for(int i = 0; i < n; ++i) a[i] = (ll)a[i] * inv_n % mod;
}
int f[M], a[M], b[M];
inline void build(int n) {
if(n == 1) {
return void(f[1] = 1);
}
if(n & 1) {
build(n - 1);
for(int i = n; i >= 1; --i) {
f[i] = f[i - 1] - (ll) (n - 1) * f[i] % mod;
if(f[i] < 0) f[i] += mod;
}
f[0] = -(ll) f[0] * (n - 1) % mod;
if(f[0] < 0) f[0] += mod;
return;
}
n >>= 1;
build(n);
int t = n + n + 1, sz = 1;
while(sz < t) sz <<= 1;
prepare(sz);
for(int i = 0; i <= n; ++i) {
a[i] = (ll) f[n - i] * fact[n - i] % mod;
}
int mul = (mod - n % mod) % mod;
for(int i = 0, p = 1; i <= n; ++i) {
b[i] = (ll) p * inv[i] % mod;
p = (ll) p * mul % mod;
}
for(int i = n + 1; i < sz; i++) a[i] = b[i] = 0;
ntt(a, sz), ntt(b, sz);
for(int i = 0; i < sz; ++i)
a[i] = (ll) a[i] * b[i] % mod;
ntt(a, sz, 1);
reverse(a, a + n + 1);
for(int i = 0; i <= n; ++i)
a[i] = (ll) a[i] * inv[i] % mod;
for(int i = n + 1; i < sz; i++) a[i] = f[i] = 0;
ntt(a, sz), ntt(f, sz);
for(int i = 0; i < sz; ++i)
f[i] = (ll) f[i] * a[i] % mod;
ntt(f, sz, 1);
}
int main(int argc, char const *argv[]) {
precalc();
int t; scanf("%d", &t); while(t--) {
int n, p, r;
scanf("%d %d %d", &n, &p, &r);
build(r);
for(int i = 0; i <= r; ++i) {
f[i] = (ll) f[i] * inv[r] % mod;
}
int ans = 0, mul;
for(int i = 1, q = p; i <= r; ++i, q = (ll) q * p % mod) {
if(q == 1) {
mul = (n + 1) % mod;
} else {
mul = (ll) (Pow(q, n + 1) - 1) * Pow(q - 1, mod - 2) % mod;
if(mul < 0) mul += mod;
}
ans += (ll) f[i] * mul % mod;
if(ans >= mod) ans -= mod;
}
printf("%d\n", ans);
}
}
Ly8vdXNyL2Jpbi9nKysgLU8yICQwIC1vICR7MCUuY3BwfSAmJiBlY2hvICItLS0tLS0tLS0tIiAmJiAuLyR7MCUuY3BwfTsgZXhpdDsKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBpaTsgCgpjb25zdCBpbnQgTiA9IDEgPDwgMjAsIE0gPSBOICogMjsgCmNvbnN0IGludCBtb2QgPSA5OTgyNDQzNTMsIGcgPSAzOwoKaW50IGZhY3RbTl0sIGludltOXTsgCgppbmxpbmUgaW50IFBvdyhpbnQgYSwgaW50IHApIHsKICAgIGludCByZXQgPSAxOyB3aGlsZShwKSB7CiAgICAgICAgaWYocCAmIDEpIHJldCA9IChsbCkgcmV0ICogYSAlIG1vZDsKICAgICAgICBhID0gKGxsKSBhICogYSAlIG1vZDsKICAgICAgICBwID4+PSAxOwogICAgfSByZXR1cm4gcmV0Owp9CgppbmxpbmUgdm9pZCBwcmVjYWxjKCkgewogICAgZmFjdFswXSA9IDE7IAogICAgZm9yKGludCBpID0gMTsgaSA8IE47ICsraSkgewogICAgICAgIGZhY3RbaV0gPSAobGwpIGZhY3RbaSAtIDFdICogaSAlIG1vZDsgCiAgICB9CiAgICBpbnZbTiAtIDFdID0gUG93KGZhY3RbTiAtIDFdLCBtb2QgLSAyKTsgCiAgICBmb3IoaW50IGkgPSBOIC0gMjsgaSA+PSAwOyAtLWkpIHsKICAgICAgICBpbnZbaV0gPSAobGwpIGludltpICsgMV0gKiAoaSArIDEpICUgbW9kOyAKICAgIH0KfQoKaW50IHJldltNXSwgd1tNXSwgaW52X247CgppbmxpbmUgdm9pZCBwcmVwYXJlKGludCAmbikgeyAKICAgIGludCBzeiA9IDMxIC0gX19idWlsdGluX2NseihuKTsgc3ogPSBhYnMoc3opOwogICAgaW50IHIgPSBQb3coZywgKG1vZCAtIDEpIC8gbik7IAogICAgaW52X24gPSBQb3cobiwgbW9kIC0gMik7CiAgICB3WzBdID0gd1tuXSA9IDE7IAogICAgZm9yKGludCBpID0gMTsgaSA8IG47ICsraSkgd1tpXSA9IChsbCl3W2kgLSAxXSAqIHIgJSBtb2Q7CiAgICBmb3IoaW50IGkgPSAxOyBpIDwgbjsgKytpKSByZXZbaV0gPSAocmV2W2kgPj4gMV0gPj4gMSkgfCAoKGkgJiAxKSA8PCAoc3ogLSAxKSk7Cn0KCmlubGluZSB2b2lkIG50dChpbnQgKmEsIGludCBuLCBpbnQgZGlyID0gMCkgeyAKICAgIGZvcihpbnQgaSA9IDE7IGkgPCBuIC0gMTsgKytpKSAKICAgICAgICBpZihpIDwgcmV2W2ldKSBzd2FwKGFbaV0sIGFbcmV2W2ldXSk7CiAgICBmb3IoaW50IG0gPSAyOyBtIDw9IG47IG0gPDw9IDEpIHsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSArPSBtKSB7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7IGogPCAobSA+PiAxKTsgKytqKSB7CiAgICAgICAgICAgICAgICBpbnQgJnUgPSBhW2kgKyBqXSwgJnYgPSBhW2kgKyBqICsgKG0gPj4gMSldOyAKICAgICAgICAgICAgICAgIGludCB0ID0gKGxsKXYgKiB3W2RpciA/IG4gLSBuIC8gbSAqIGogOiBuIC8gbSAqIGpdICUgbW9kOwogICAgICAgICAgICAgICAgdiA9IHUgLSB0IDwgMCA/IHUgLSB0ICsgbW9kIDogdSAtIHQ7CiAgICAgICAgICAgICAgICB1ID0gdSArIHQgPj0gbW9kID8gdSArIHQgLSBtb2QgOiB1ICsgdDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0gaWYoZGlyKSBmb3IoaW50IGkgPSAwOyBpIDwgbjsgKytpKSBhW2ldID0gKGxsKWFbaV0gKiBpbnZfbiAlIG1vZDsKfQoKaW50IGZbTV0sIGFbTV0sIGJbTV07IAoKaW5saW5lIHZvaWQgYnVpbGQoaW50IG4pIHsKICAgIGlmKG4gPT0gMSkgewogICAgICAgIHJldHVybiB2b2lkKGZbMV0gPSAxKTsgCiAgICB9CiAgICBpZihuICYgMSkgewogICAgICAgIGJ1aWxkKG4gLSAxKTsgCiAgICAgICAgZm9yKGludCBpID0gbjsgaSA+PSAxOyAtLWkpIHsKICAgICAgICAgICAgZltpXSA9IGZbaSAtIDFdIC0gKGxsKSAobiAtIDEpICogZltpXSAlIG1vZDsKICAgICAgICAgICAgaWYoZltpXSA8IDApIGZbaV0gKz0gbW9kOyAKICAgICAgICB9CiAgICAgICAgZlswXSA9IC0obGwpIGZbMF0gKiAobiAtIDEpICUgbW9kOyAKICAgICAgICBpZihmWzBdIDwgMCkgZlswXSArPSBtb2Q7IAogICAgICAgIHJldHVybjsgCiAgICB9CgogICAgbiA+Pj0gMTsgCiAgICBidWlsZChuKTsKCiAgICBpbnQgdCA9IG4gKyBuICsgMSwgc3ogPSAxOyAKICAgIHdoaWxlKHN6IDwgdCkgc3ogPDw9IDE7IAogICAgcHJlcGFyZShzeik7IAoKICAgIGZvcihpbnQgaSA9IDA7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgYVtpXSA9IChsbCkgZltuIC0gaV0gKiBmYWN0W24gLSBpXSAlIG1vZDsgCiAgICB9CgogICAgaW50IG11bCA9IChtb2QgLSBuICUgbW9kKSAlIG1vZDsgCiAgICBmb3IoaW50IGkgPSAwLCBwID0gMTsgaSA8PSBuOyArK2kpIHsKICAgICAgICBiW2ldID0gKGxsKSBwICogaW52W2ldICUgbW9kOyAKICAgICAgICBwID0gKGxsKSBwICogbXVsICUgbW9kOwogICAgfQoKICAgIGZvcihpbnQgaSA9IG4gKyAxOyBpIDwgc3o7IGkrKykgYVtpXSA9IGJbaV0gPSAwOyAKCiAgICBudHQoYSwgc3opLCBudHQoYiwgc3opOyAKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBzejsgKytpKQogICAgICAgIGFbaV0gPSAobGwpIGFbaV0gKiBiW2ldICUgbW9kOwogICAgbnR0KGEsIHN6LCAxKTsgCgogICAgcmV2ZXJzZShhLCBhICsgbiArIDEpOyAKICAgIGZvcihpbnQgaSA9IDA7IGkgPD0gbjsgKytpKQogICAgICAgIGFbaV0gPSAobGwpIGFbaV0gKiBpbnZbaV0gJSBtb2Q7IAogICAgZm9yKGludCBpID0gbiArIDE7IGkgPCBzejsgaSsrKSBhW2ldID0gZltpXSA9IDA7IAoKICAgIG50dChhLCBzeiksIG50dChmLCBzeik7IAogICAgZm9yKGludCBpID0gMDsgaSA8IHN6OyArK2kpIAogICAgICAgIGZbaV0gPSAobGwpIGZbaV0gKiBhW2ldICUgbW9kOwogICAgbnR0KGYsIHN6LCAxKTsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgY29uc3QgKmFyZ3ZbXSkgewogICAgcHJlY2FsYygpOyAKICAgIGludCB0OyBzY2FuZigiJWQiLCAmdCk7IHdoaWxlKHQtLSkgewogICAgICAgIGludCBuLCBwLCByOyAKICAgICAgICBzY2FuZigiJWQgJWQgJWQiLCAmbiwgJnAsICZyKTsgCgogICAgICAgIGJ1aWxkKHIpOwoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDw9IHI7ICsraSkgewogICAgICAgICAgICBmW2ldID0gKGxsKSBmW2ldICogaW52W3JdICUgbW9kOwogICAgICAgIH0KCiAgICAgICAgaW50IGFucyA9IDAsIG11bDsKICAgICAgICBmb3IoaW50IGkgPSAxLCBxID0gcDsgaSA8PSByOyArK2ksIHEgPSAobGwpIHEgKiBwICUgbW9kKSB7CiAgICAgICAgICAgIGlmKHEgPT0gMSkgewogICAgICAgICAgICAgICAgbXVsID0gKG4gKyAxKSAlIG1vZDsgCiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBtdWwgPSAobGwpIChQb3cocSwgbiArIDEpIC0gMSkgKiBQb3cocSAtIDEsIG1vZCAtIDIpICUgbW9kOyAKICAgICAgICAgICAgICAgIGlmKG11bCA8IDApIG11bCArPSBtb2Q7IAogICAgICAgICAgICB9CiAgICAgICAgICAgIGFucyArPSAobGwpIGZbaV0gKiBtdWwgJSBtb2Q7CiAgICAgICAgICAgIGlmKGFucyA+PSBtb2QpIGFucyAtPSBtb2Q7IAogICAgICAgIH0KCiAgICAgICAgcHJpbnRmKCIlZFxuIiwgYW5zKTsKICAgIH0KfQ==