Series Sum

Given are two integers $k$ and $p$. Calculate

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

where ${n \choose k}$ denotes a binomial coefficient that equals to $\displaystyle \frac{n!}{k! \cdot (n - k)!}$.

It is guaranteed that the result can be represented in the form of $\frac{r}{q}$ where $r$ and $q$ are positive coprime integers and $q \neq 0$. Find $r \cdot q^{-1}$ modulo $998\,244\,353$.

The first line contains an integer $t$ ($1 \le t \le 2112$), the number of test cases. The test cases follow.

Each test case is described by a single line containing two integers $k$ and $p$ ($k, p \ge 1$; $p \cdot k \le 10^6$).

The total sum of $p \cdot k$ over all test cases does not exceed $10^6$.

For each test case, print a single line containing the integer $r \cdot q^{-1} \bmod 998\,244\,353$: the result of the calculation.