問題文

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

第 $i$ 項 を $E_i$ とすると、

• $E_1 = 1$
• $E_i = E_{i-1} + \displaystyle \sum_{1 \leq k \leq i - 1} E_k \: (i \geq 2)$

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

制約

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

入力

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

出力

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

入出力例

4

13

• $E_1 = 1$
• $E_2 = 1 + (1) = 2$
• $E_3 = 2 + (1 + 2) = 5$
• $E_4 = 5 + (1 + 2 + 5) = 13$

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

539438

99957518

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