← 返回题目列表

Codeforces · 2039/E

E. Shohag 喜欢反转

中文机器翻译题面 查看原题

Shohag 有一个整数数组 $$$a$$$。最初 $$$a = [0, 1]$$$。他可以重复执行以下操作任意多次:

- 令 $$$k$$$ 为当前数组 $$$a$$$ 中的反转数 $$$^{\text{*}}$$$。
- 在 $$$a$$$ 中的任意位置插入 $$$k$$$,包括开头或结尾。

例如,如果 $$$a = [4, 6, 2, 4]$$$,则反转次数为 $$$k = 3$$$。所以 Shohag 运算后可以得到如下数组: $$$[\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$$$,帮助 Shohag 计算,模 $$$998\,244\,353$$$,执行操作后可以获得的长度为 $$$n$$$ 的不同数组的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个整数 - 可能数组的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #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]$$$。