1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| const int N = 2005;
int n, m, k;
ll f[N][N];
const ll mod = 998244353;
ll fpow(ll x, ll r)
{
ll result = 1;
while (r)
{
if (r & 1)result = result * x % mod;
r >>= 1;
x = x * x % mod;
}
return result;
}
int main()
{
int p, q, u, v, w, x, y, z, T;
f[0][0] = 1;
for (int i = 1; i <= N - 5; i++)
for (int j = 1; j <= i; j++)
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j] * j) % mod;
cin >> T;
while (T--)
{
scanf("%d%d%d", &n, &m, &k);
ll ans = 0, now = 1;
for (int i = 0; i <= min(n, k); i++)
{
ans = (ans + now * f[k][i] % mod * fpow(m, n - i) % mod * fpow((m + 1) / 2, i)) % mod;
now = now * (n - i) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
|