P4921 [MtOI2018] Couples? Burn Them for Me!

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

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 $2 \times n$ seats in total. Now, each person will randomly sit in one seat, and all $2 \times n$ seats will be occupied. If a couple sits in the same row, then we call this couple harmonious. Your task is to compute, for $k = 0, 1, \ldots, n$, how many different seating arrangements satisfy that there are **exactly** $k$ harmonious couples. 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 easy to see that there are $(2n)!$ different seating arrangements in total. Since the answer may be large, output the result modulo $998244353$.

The input contains multiple test cases. The first line contains one positive integer $T(1 \leq T \leq 1000)$, indicating the number of test cases. The next $T$ lines each contain one positive integer $n(1 \leq n \leq 1000)$.

For each test case, output a total of $n + 1$ lines. Each line contains one integer, which represents the number of seating arrangements with exactly $k$ harmonious couples for $k = 0, 1, \ldots, n$.

### Subtasks This problem has only one test point with $T = 1000$... so forget brute force! ### Source [MtOI2018 迷途の家の水题大赛](https://www.luogu.org/contest/11260) T2. Problem setter: Imagine. 50167. Translated by ChatGPT 5