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

  • 1T105
  • 1n106

Output Format

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

Sample Input 1

2
2
7

Sample Output 1

3
377

Hints

Problem Source

IOICamp 2024 Day6 pH

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