[MtOI2018]情侣?给我烧了!(加强版)

题目背景

FFF 本题原版:[P4921](https://www.luogu.com.cn/problem/P4921)

题目描述

有 $n$ 对情侣来到电影院观看电影。在电影院,恰好留有 $n$ 排座位,每排包含 $2$ 个座位,共 $2×n$ 个座位。 现在,每个人将会随机坐在某一个位置上,且恰好将这 $2 × n$ 个座位坐满。 如果一对情侣坐在了同一排的座位上,那么我们称这对情侣是和睦的。 你的任务是求出当 $k = 0, 1, ... , n$ 时,共有多少种不同的就坐方案满足**恰好**有 $k$ 对情侣是和睦的。 两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现,一共会有 $(2n)!$ 种不同的就坐方案。 由于结果可能较大,因此输出对 $998244353$ 取模的结果。

输入输出格式

输入格式


输入包含多组数据。 输入的第 $1$ 行包含 $1$ 个正整数 $T(1 \leq T \leq 1000)$,表示数据的组数。 接下来 $T$ 行,每行包含 $1$ 个正整数 $n(1 \leq n \leq 1000)$。

输出格式


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

输入输出样例

输入样例 #1

5
1 1
2 0
2 2
2333 666
2333333 1000000

输出样例 #1

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 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T2 加强版 出题人:Imagine 50167