급수의 합

두 정수 $k$와 $p$가 주어진다. 다음 값을 구하라.

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

여기서 ${n \choose k}$는 이항 계수이며 $\displaystyle \frac{n!}{k! \cdot (n-k)!}$와 같다.

결과는 $\frac{r}{q}$ 꼴로 나타낼 수 있으며, $r$과 $q$는 서로소인 양의 정수이고 $q \neq 0$이다. $r \cdot q^{-1}$을 998244353으로 나눈 나머지를 구하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 2112$)가 주어진다. 각 테스트 케이스는 정수 $k$와 $p$가 적힌 한 줄이다 ($k, p \ge 1$, $p \cdot k \le 10^6$). 모든 테스트 케이스의 $p \cdot k$ 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 $r \cdot q^{-1} \bmod 998244353$의 값을 한 줄에 출력하라.