Series Sum

Given two integers $k$ and $p$, calculate the following value.

$\sum\limits_{n = k}^{\infty} \frac{{n \choose k}^p}{2^n}$

Here ${n \choose k}$ is the binomial coefficient, equal to $\displaystyle \frac{n!}{k! \cdot (n-k)!}$.

The result can be written as $\frac{r}{q}$, where $r$ and $q$ are positive coprime integers and $q \neq 0$. Output $r \cdot q^{-1}$ modulo 998244353.

The first line contains an integer $t$ ($1 \le t \le 2112$), the number of test cases. Each test case is one line with two integers $k$ and $p$ ($k, p \ge 1$, $p \cdot k \le 10^6$). The sum of $p \cdot k$ over all test cases does not exceed $10^6$.

For each test case, print on a single line the value $r \cdot q^{-1} \bmod 998244353$.