問題文

以下のような数列 EE を「ダルマ数列」と定義します。

ii 項 を EiE_i とすると、

  • E1=1E_1 = 1
  • Ei=Ei1+1ki1Ek(i2)E_i = E_{i-1} + \displaystyle \sum_{1 \leq k \leq i - 1} E_k \: (i \geq 2)

「ダルマ数列」の第 NN 項を求めてください。
なお、答えがとても大きくなることがあるので、998244353998244353 で割った余りを出力してください。

制約

  • 1N10121 \leq N \leq 10^{12}
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN

出力

問題の答えを一行に出力せよ。

入出力例

入力例1
4
出力例1
13
  • E1=1E_1 = 1
  • E2=1+(1)=2E_2 = 1 + (1) = 2
  • E3=2+(1+2)=5E_3 = 2 + (1 + 2) = 5
  • E4=5+(1+2+5)=13E_4 = 5 + (1 + 2 + 5) = 13

と計算できるため、1313 と出力します。

入力例2
539438
出力例2
99957518

998244353998244353 で割った余りを出力することに注意してください。

Submit


Go (1.21)