Consider the grid $$$\mathbb{Z}^k$$$, that is, the set of points of the form $$$(a_1, \dots, a_k)$$$ with $$$a_i$$$ being integers. For example, for $$$k=2$$$, this is the usual grid one would find on an infinitely extended graph paper. Given an $$$n$$$, the task is to calculate the number of paths that start from the origin and return to it in $$$2n$$$ steps, where each move consists of adding or subtracting one to any of the coordinates. The result should be given modulo $$$998244353$$$.
The input consists of multiple cases. The first line will contain a natural number $$$t$$$, the number of cases.
Each case will consist of a line with the integers $$$n$$$ and $$$k$$$ separated by a space.
The output should be a natural number for each case, representing the number of distinct paths that return to the origin modulo $$$998244353$$$.
$$$1 \leq t \leq 200000$$$
21 points: $$$1 \leq n \leq 10^5$$$, $$$k = 1$$$
12 points: $$$1 \leq n \leq 30$$$, $$$k \leq 5$$$
43 points: $$$1 \leq n \leq 100$$$, $$$k \leq 100$$$
24 points: $$$1 \leq n \leq 10^5$$$, $$$k \leq 2$$$
3 1 2 10 1 10 3
4 184756 975531138
