题目背景

FFF

本题原版：P4921

题目描述

有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2n$ 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 $2n$ 个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出共有多少种不同的就坐方案满足恰好有 k 对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2n)!$ 种不同的就坐方案。

由于结果可能较大，因此输出对 $998244353$ 取模的结果。

输入格式

输入包含多组数据。

输入的第 $1$ 行包含 $1$ 个正整数 $T$，表示数据的组数。

接下来 $T$ 行，每行包含 $2$ 个正整数 $n,k$。

输出格式

输出共 $T$ 行。

对于每组输入数据，输出共 $1$ 行，包含 $1$ 个整数，表示恰好有 $k$ 对情侣和睦的就坐方案数。

5
1 1
2 0
2 2
2333 666
2333333 1000000

2
16
8
798775522
300377435

提示

子任务

对于 $10 \%$ 的数据，满足 $1 \leq T \leq 10, 1 \leq n \leq 5$。

对于 $40 \%$ 的数据，满足 $1 \leq n \leq 3 \times 10^3$。

对于 $100 \%$ 的数据，满足 $1 \leq T \leq 2 \times 10^5, 1 \leq n \leq 5 \times 10^6, 0 \leq k \leq n$。

题目来源

MtOI2018 迷途の家の水题大赛 T2 加强版

出题人：Imagine

50167