Background

FFF.

Enhanced version of this problem: P4931.

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

Input Format

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

Output Format

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

2
1
2

0
2
16
0
8

Hint

Subtasks

This problem has only one test point with $T = 1000$... so forget brute force!

Source

MtOI2018 迷途の家の水题大赛 T2.

Problem setter: Imagine.

Translated by ChatGPT 5