CF1716F Bags with Balls

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.

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 $ ).

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 $ .