TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (19/19)

Submission's AC Ratio

75.3% (55/73)

Tags

Description

兩個人在玩遊戲,一開始會有一個整數 $n$。

第一個玩家可以把 $n$ 拆成一些正整數的和,比如, $n=3$ 時,有 $1+1+1$, $1+2$, $2+1$, $3$ 這四種拆法。

第二個玩家則要算出拆出的數字的乘積,而你想要知道每一種拆法對應到的乘積的和是多少。

因為數字可能很大,算出答案除以 $998244353$ 的餘數即可。

Input Format

輸入第一行有一個正整數 $T$,代表有 $T$ 筆子測試資料。

對於每一筆子測試資料,輸入只有一行,這行有一個整數 $n$,代表詢問的 $n$。

  • $1\le T\le 10^ 5$
  • $1\le n \le 10^ 6$

Output Format

對於每一筆子測試資料,輸出一行,代表要計算的和除以 $998244353$ 的餘數。

Sample Input 1

2
2
7

Sample Output 1

3
377

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~3 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2