AT_ttpc2023_a Numerous Elimination

選手 $ 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 $

答えを出力せよ。

### Sample Explanation 1 番号の小さい選手が試合に勝つものとすると、以下のように大会が進行します。 列 $ 0 $ 列 $ 1 $ 列 $ 2 $ 説明 $ \underline{1, 2}, 3 $ 選手 $ 1, 2 $ が試合を行い、選手 $ 1 $ が列 $ 1 $ に、選手 $ 2 $ が列 $ 0 $ に並ぶ $ \underline{3, 2} $ $ 1 $ 選手 $ 3, 2 $ が試合を行い、選手 $ 2 $ が列 $ 1 $ に、選手 $ 3 $ が列 $ 0 $ に並ぶ $ 3 $ $ \underline{1, 2} $ 選手 $ 1, 2 $ が試合を行い、選手 $ 1 $ が列 $ 2 $ に、選手 $ 2 $ が列 $ 0 $ に並ぶ $ \underline{3, 2} $ $ 1 $ 選手 $ 3, 2 $ が試合を行い、選手 $ 2 $ が列 $ 1 $ に、選手 $ 3 $ が列 $ 0 $ に並ぶ $ 3 $ $ 2 $ $ 1 $ どの列にもちょうど $ 1 $ 人の選手が並んでいるので、終了する 試合は $ 4 $ 回行われるので、 $ 4 $ を出力します。 ### Constraints - $ N $ は整数 - $ 1 \le N \le 10^5 $