Bags with Balls
Contest: Educational Codeforces Round 133 (Rated for Div. 2)
Difficulty rating: 2500
Tags: combinatorics, dp, math, number theory

There are $$$n$$$ bags, each bag contains $$$m$$$ balls with numbers from $$$1$$$ to $$$m$$$. For every $$$i \in [1, m]$$$, there is exactly one ball with number $$$i$$$ in each bag.

You have to take exactly one ball from each bag (all bags are different, so, for example, taking the ball $$$1$$$ from the first bag and the ball $$$2$$$ from the second bag is not the same as taking the ball $$$2$$$ from the first bag and the ball $$$1$$$ from the second bag). After that, you calculate the number of balls with odd numbers among the ones you have taken. Let the number of these balls be $$$F$$$.

Your task is to calculate the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of one line containing three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m \le 998244352$$$; $$$1 \le k \le 2000$$$).

Output format:
For each test case, print one integer — the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag. Since it can be huge, print it modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000

Example output:
1028
1
3
729229716
652219904

Editorial:
The main idea of this problem is to use a technique similar to "contribution to the sum". We will model the value of $$$F^k$$$ as the number of tuples $$$(i_1, i_2, \dots, i_k)$$$, where each element is an index of a bag from which we have taken an odd ball. Let $$$G(t)$$$ be the number of ways to take balls from bags so that all elements from tuple $$$t$$$ are indices of bags with odd balls; then, the answer to the problem can be calculated as the sum of $$$G(t)$$$ over all possible tuples $$$t$$$.
First of all, let's obtain a solution in $$$O(k^2)$$$ per test case. We need to answer the following questions while designing a solution to the problem:
• How do we calculate $$$G(t)$$$ for a given tuple?
• How do we group tuples and iterate through them?
The first question is not that difficult. Every element from the tuple $$$(i_1, i_2, \dots, i_k)$$$ should be an index of a bag from which we have taken an odd ball; so, for every bag appearing in the tuple, we can take only a ball with odd number; but for every bag not appearing in the tuple, we can choose any ball. So, if the number of distinct elements in a tuple is $$$d$$$, then $$$G(t)$$$ for the tuple can be calculated as $$$\lceil \frac{m}{2}\rceil^d \cdot m^{n-d}$$$.
This actually gives as a hint for the answer to the second question: since $$$G(t)$$$ depends on the number of distinct elements in the tuple, let's try to group the tuples according to the number of distinct elements in them. So, the answer will be calculated as $$$\sum\limits_{i=1}^{k} H(i) \lceil \frac{m}{2}\rceil^i \cdot m^{n-i}$$$, where $$$H(i)$$$ is the number of tuples with exactly $$$i$$$ different elements.
How do we calculate $$$H(i)$$$? First of all, if $$$i > n$$$, then $$$H(i)$$$ is obviously $$$0$$$. Otherwise, we can use the following recurrence: let $$$dp_{i,j}$$$ be the number of tuples of $$$i$$$ elements with $$$j$$$ distinct ones; then:
• if $$$i = 1$$$ and $$$j = 1$$$, $$$dp_{i,j} = n$$$ (for a tuple with one element, there are $$$n$$$ ways to choose it);
• if $$$i = 1$$$ and $$$j \ne 1$$$, $$$dp_{i,j} = 0$$$;
• if $$$i > 1$$$ and $$$j = 1$$$, $$$dp_{i,j} = dp_{i-1,j}$$$ (there is only one distinct element, and it was already chosen);
• if $$$i > 1$$$ and $$$j > 1$$$, $$$dp_{i,j} = dp_{i-1,j} \cdot j + dp_{i-1,j-1} \cdot (n-j+1)$$$ (we either add an element which did not belong to the tuple, and there are $$$n-j+1$$$ ways to choose it, or we add an already existing element, and there are $$$j$$$ ways to choose it).
Obviously, this recurrence can be calculated in $$$O(k^2)$$$ with dynamic programming, so we get a solution in $$$O(k^2)$$$ per test case.
How do we speed this up? Let's change the way we calculate $$$H(i)$$$. Instead of considering tuples with values from $$$1$$$ to $$$n$$$, we will consider only tuples where values are from $$$1$$$ to $$$k$$$, and the first appearance of a value $$$i$$$ is only after the first appearance of the value $$$i-1$$$. So, these tuples actually represent a way to split a set of integers $$$\{1, 2, \dots, n\}$$$ into several subsets; so they are the Stirling numbers of the second kind, and we can calculate them in $$$O(k^2)$$$ with dynamic programming outside of processing the test cases.
How do we calculate $$$H(i)$$$ using these values? If we use $$$i$$$ distinct integers as the elements of the tuple, there are $$$n$$$ ways to choose the first one, $$$n-1$$$ ways to choose the second one, etc. — so $$$H(i) = S(k,i) \cdot \prod \limits_{j=0}^{i-1} (n-j)$$$, where $$$S(k, i)$$$ is the Stirling number of the second kind for the parameters $$$k$$$ and $$$i$$$. We can maintain the values of $$$\prod \limits_{j=0}^{i-1} (n-j)$$$ and $$$\lceil \frac{m}{2}\rceil^i \cdot m^{n-i}$$$ while iterating on $$$i$$$ from $$$1$$$ to $$$k$$$, and that gives us a way to solve the problem in $$$O(k)$$$ per test case.
Overall complexity: $$$O(k^2)$$$ for precalculation and $$$O(k)$$$ per test case.