CF2039E Shohag Loves Inversions

# Shohag Loves Inversions 给你一个数列，初始数列为 $ a = [0, 1] $ ，现在重复进行以下操作若干次: - 将当前数组中逆序对个数k插入当前数组中任意一个位置，包括开头或者结尾。 举个例子, 如果 $ a = [4, 6, 2, 4] $ , 则逆序对个数是 $ k = 3 $ . 所以可以通过操作，得到以下数组: $ [\textbf{3}, 4, 6, 2, 4] $ , $ [4, \textbf{3}, 6, 2, 4] $ , $ [4, 6, \textbf{3}, 2, 4] $ , $ [4, 6, 2, \textbf{3}, 4] $ , 和$ [4, 6, 2, 4, \textbf{3}] $ 。 给一个整数 $ n $，求通过操作可以得到多少种长度为$ n $的不同数列，方案数对对 $ 998\,244\,353 $ 取模。 逆序对的对数就是有多少个二元组，满足 $ i < j $ 并且 $ a_i > a_j $ 。

第一行给出一个整数$ t $ ( $ 1 \le t \le 10^4 $ )，表示有多少组数据。 每行给出一个整数 $ n $ ( $ 2 \le n \le 10^6 $ ) 可以保证n的和在所有测试用例中不超过$ 10^6 $ 。

对于每一个测试点, 输出一个整数 — 对 $ 998\,244\,353 $ 取模。 ## 样例 #1 ### 样例输入 #1 ``` 4 4 2 7 69 ``` ### 样例输出 #1 ``` 5 1 682 325188814 ```

对于第一个样例, 以下$ 5 $种数列可以通过操作得到 - $ [0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, 1, \textbf{0}] $ , - $ [0, 1] \rightarrow [0, \textbf{0}, 1] \rightarrow [0, 0, \textbf{0}, 1] $ , - $ [0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, 0, \textbf{1}] $ , - $ [0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [0, 1, \textbf{1}, 0] $ , - $ [0, 1] \rightarrow [0, 1, \textbf{0}] \rightarrow [\textbf{1}, 0, 1, 0] $ .