408466: GYM103145 A Matrix

Fill an $$$n\times n$$$ matrix with numbers in $$$[1,n^2]$$$, where each number occurs exactly once.

For a fixed number filling method, let $$$a_i$$$ be the mininum number in the $$$i$$$th row, and $$$S=\{a_1,a_2,...,a_n\}\cap\{1,2,...,n\}$$$.

You need to calculate $$$\sum |S|\pmod {998244353}$$$, i.e. the sum of the size of $$$S$$$ over all possible methods.

This problem contains multiple test cases.

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 30$$$).

Then $$$T$$$ cases follow, each of which contains a single interger $$$n$$$ ($$$1\leq n\leq 5000$$$).

For each test case, output one line contains the value of $$$\sum |S|\pmod {998244353}$$$.

1
2

40