Background

FFF.

Original version of this problem: P4921.

Problem Description

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$.

Input Format

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 Format

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.

5
1 1
2 0
2 2
2333 666
2333333 1000000

2
16
8
798775522
300377435

Hint

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 迷途の家の水题大赛 T2 Enhanced Version.

Problem setter: Imagine.

Translated by ChatGPT 5