/ 
実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
長さ N の整数列 A=(0,0,\ldots,0) があります。 次の操作を行える限り、繰り返し行います。
- 1\le i\lt j\le |A| かつ A_i=A_j を満たす整数の組 (i,j) を選ぶ。
- A_i,A_j を列から取り除く。
- 取り除く直前に A_i と A_j の間にあったすべての要素に 1 を加える。
ここで |A| は、その時点での列 A の長さを表します。
操作を行えなくなったときの列としてあり得るものの個数を 998244353 で割った余りを求めてください。 最終的な列が同じならば、操作の過程が異なっても区別しません。 長さ 0 の列も 1 つの列として数えます。
制約
- 1 \le N \le 2 \times 10^5
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
1
出力例 1
1
操作を行えないため、最終的な列は (0) の 1 個です。
入力例 2
5
出力例 2
3
最終的な列としてあり得るものは、(0)、(1)、(2) の 3 個です。
入力例 3
7
出力例 3
8
操作の選び方によって、8 個の異なる列を得られます。
入力例 4
200000
出力例 4
159211719
答えを 998244353 で割った余りを求めることに注意してください。
Score : 800 points
Problem Statement
There is an integer sequence A=(0,0,\ldots,0) of length N. The following operation is repeated as long as it can be performed.
- Choose a pair of integers (i,j) satisfying 1\le i\lt j\le |A| and A_i=A_j.
- Remove A_i and A_j from the sequence.
- Add 1 to every element that was between A_i and A_j immediately before the removal.
Here, |A| denotes the length of the sequence A at that point.
Find the number, modulo 998244353, of possible sequences when no more operations can be performed. If the final sequences are the same, they are not distinguished even if the process of operations differs. A sequence of length 0 is also counted as one sequence.
Constraints
- 1 \le N \le 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Output the answer.
Sample Input 1
1
Sample Output 1
1
No operation can be performed, so there is one possible final sequence: (0).
Sample Input 2
5
Sample Output 2
3
There are three possible final sequences: (0), (1), (2).
Sample Input 3
7
Sample Output 3
8
Depending on the choices made during the operations, eight different sequences can be obtained.
Sample Input 4
200000
Sample Output 4
159211719
Be sure to find the count modulo 998244353.