[Solution] Bags with Balls Codeforces Solution

F. Bags with Balls

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

There are n$n$ bags, each bag contains m$m$ balls with numbers from 1$1$ to m$m$. For every i∈[1,m]$i\in [1,m]$, there is exactly one ball with number i$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$1$ from the first bag and the ball 2$2$ from the second bag is not the same as taking the ball 2$2$ from the first bag and the ball 1$1$ from the second bag). After that, you calculate the number of balls

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 with odd numbers among the ones you have taken. Let the number of these balls be F$F$.

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

Input

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

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

Output

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