First we make $f[i]$ as the probability of hit $i$ times among $k$ times in a round. We can also get the probability of getting 1 life point back.

So we get $p[i][j]$ as the probability of changing life points from $i$ to $j$ in one round.

Then we can list the expectation of answers when our target have $i$ points left. That is:

Notice that when one has $n$ points, he cannot get life increased.

As we deal the expression, we would find that all expectations only have to do with $E_1$ and $E_2$, so we can calculate the factor before $E_1$ and $E_2$ for each $i$ in range $[1,n]$.

int n, k, m, P; ll f[maxn], p[maxn][maxn], a[maxn], b[maxn];

inlineintrd(){ registerint x = 0, c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return x; } inline ll quick_power(ll base, ll index){ ll ret = 1; while (index) { if (index & 1) ret = ret * base % mod; index >>= 1; base = base * base % mod; } return ret; } inlinevoidinc(ll &lhs, const ll &rhs){ lhs += rhs; if (lhs >= mod) lhs -= mod; }

intmain(){ int T = rd(); while (T--) { n = rd(); P = rd(); m = rd(); k = rd(); if (!k) { puts("-1"); continue; } if (m == 0) { int rnd = 0; if (k == 1) puts("-1"); else { while (P > 0) rnd++, P = min(n, P + 1) - k; printf("%d\n", rnd); } continue; } for (int i = 0; i <= n; ++i) f[i] = 0; ll Inv_mpls = quick_power(m + 1, mod - 2); f[0] = 1; int lim = min(n - 1, k); for (int i = 1; i <= lim; ++i) f[i] = f[i - 1] * quick_power(i, mod - 2) % mod * (k - i + 1) % mod; for (int i = 0; i <= lim; ++i) f[i] = f[i] * quick_power(m, k - i) % mod * quick_power(quick_power(m + 1, k), mod - 2) % mod; if (k >= n) { f[n] = 1; for (int i = 0; i < n; ++i) f[n] = (f[n] - f[i] + mod) % mod; } for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) p[i][j] = 0; for (int i = 1; i < n; ++i) for (int j = 1; j <= i + 1; ++j) inc(p[i][j], (Inv_mpls * f[i - j + 1] + m * Inv_mpls % mod * f[i - j]) % mod); for (int i = 1; i <= n; ++i) inc(p[n][i], f[n - i]); for (int i = 0; i <= n; ++i) a[i] = b[i] = 0; a[1] = 1; for (int i = 1; i < n; ++i) { ll suma = a[i], sumb = (b[i] - 1 + mod) % mod; for (int j = 1; j <= i; ++j) suma = (suma - p[i][j] * a[j] % mod + mod) % mod; for (int j = 1; j <= i; ++j) sumb = (sumb - p[i][j] * b[j] % mod + mod) % mod; ll inv = quick_power(p[i][i + 1], mod - 2); a[i + 1] = suma * inv % mod; b[i + 1] = sumb * inv % mod; } ll suma = a[n], sumb = (1 - b[n] + mod) % mod; for (int i = 1; i <= n; ++i) { suma = (suma - p[n][i] * a[i] % mod + mod) % mod; } for (int i = 1; i <= n; ++i) { sumb = (sumb + p[n][i] * b[i]) % mod; } ll x = 1ll * sumb * quick_power(suma, mod - 2) % mod; ll ans = (a[P] * x + b[P]) % mod; printf("%lld\n", ans); } return0; }