P6043 "ACOI2020" Study Trip

 Not long after the first semester begins, everyone in Class E is going on a study trip.

Now, six people—Akabane Karma, Sugino Tomohito, Okuda Manami, Kayano Kaede, Kanzaki Yukiko, and Shiota Nagisa—form a group. They will go on an assassination trip in Kyoto. Their goal is still to snipe and kill their teacher. The government has also sent a professional sniper, "Akame no Eye". While completing the mission, they want the happiness value to be as large as possible. The clever Kanzaki Yukiko (Kanzaki Yukiko) finally worked out the expression for the happiness value. Shockingly, the happiness value is actually related to the number of sightseeing spots in the trip and the number of times they assassinate their teacher. Suppose they pass through $n$ sightseeing spots and assassinate their teacher $m$ times, and define: $$ \Gamma(a,b)=\left\{ \begin{aligned} & 1,a>b&\\ & \prod_{i=a}^b i,a \le b&\\ \end{aligned} \right. $$ Then the happiness value is: $$ \sum_{i=0}^m \lgroup \frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n) \rgroup $$ **We guarantee** that $\frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n)$ **is an integer.** Now they have $T$ questions to ask you. If they pass through $n$ sightseeing spots and assassinate their teacher $m$ times, can you tell them the happiness value? **Since the answer may be very large, output the answer modulo $998244353$.**

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: There is only one line with two integers $n$ and $m$.

For each test case, output one line containing one integer: the happiness value modulo $998244353$ when they pass through $n$ sightseeing spots and assassinate their teacher $m$ times. #### The sample has been updated.

#### Constraints **This problem uses bundled testdata.** - Subtask 1 (10 points): $T \leq 10$, $n,m \leq 10$. - Subtask 2 (20 points): $T \leq 100$, $n,m \leq 5 \times 10^4$. - Subtask 3 (30 points): $T \leq 50$, $n,m \leq 9 \times 10^8$. - Subtask 4 (40 points): No special constraints on the testdata. For $100\%$ of the testdata, $m \leq n$, $1 \leq T \le 10^2$, $1 \leq n,m \leq 9 \times 10^8$. --- #### Notes **The time limit is 2 s for the test points in the third subtask, and 5 s for the test points in the fourth subtask.** Translated by ChatGPT 5