問題文

選手 1, 2, \dots, N の N 人の選手が参加する大会が行われます。

会場には列 0, 1, \dots, N-1 の N 個の列が用意されており、列 i\ (0 \le i \le N - 1) に並んでいる選手はその時点で i 連勝中であることを表します。

大会開始時点では、選手は列 0 の先頭から順に選手 1, 2, \dots, N の順で並んでいます。

大会では、次の手順に従って各選手の順位を決めます。

1. どの列にもちょうど 1 人の選手が並んでいるとき、列 i に並んでいる選手の順位は N-i 位である。このとき手順を終了する。
2. 2 人以上の選手が並んでいる列の中で最も番号の小さい列を列 l とする。
3. 列 l の先頭 2 人は列から抜け、その 2 人で試合を行う。試合に勝った方は列 l+1 の後ろに並び、負けた方は列 0 の後ろに並ぶ。
4. 手順 1. に戻る。

この大会で行われる試合の回数を 998244353 で割ったあまりを求めてください。

ただし、試合に引き分けはないものとします。また、各試合の結果に依らず答えは一意に定まることが証明できます。

制約

• N は整数
• 1 \le N \le 10^5

入力例 1

3

出力例 1

4

番号の小さい選手が試合に勝つものとすると、以下のように大会が進行します。

試合は 4 回行われるので、4 を出力します。

入力例 2

5

出力例 2

26

入力例 3

100000

出力例 3

538161387