P4931 [MtOI2018] Couples? Burn Them for Me! (Enhanced Version)

FFF. Original version of this problem: [P4921](https://www.luogu.com.cn/problem/P4921).

There are $n$ couples who come to a cinema to watch a movie. In the cinema, there are exactly $n$ rows of seats, and each row contains $2$ seats, so there are $2n$ seats in total. Now, everyone will randomly sit in one seat, and exactly all $2n$ seats will be occupied. If a couple sits in the same row, then we call this couple harmonious. Your task is to find how many different seating arrangements satisfy that **exactly** $k$ couples are harmonious. Two seating arrangements are different if and only if there exists at least one person who sits in a different seat in the two arrangements. It is not hard to see that there are $(2n)!$ different seating arrangements in total. Since the answer may be large, output it modulo $998244353$.

The input contains multiple test cases. The first line contains one positive integer $T$, the number of test cases. The next $T$ lines each contain two positive integers $n, k$.

Output $T$ lines. For each test case, output one line containing one integer, the number of seating arrangements in which exactly $k$ couples are harmonious.

### Subtasks For $10\%$ of the testdata, $1 \leq T \leq 10$ and $1 \leq n \leq 5$. For $40\%$ of the testdata, $1 \leq n \leq 3 \times 10^3$. For $100\%$ of the testdata, $1 \leq T \leq 2 \times 10^5$, $1 \leq n \leq 5 \times 10^6$, and $0 \leq k \leq n$. ### Source [MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T2 Enhanced Version. Problem setter: Imagine. 50167. Translated by ChatGPT 5