外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

L - Pat and Release

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、nekooooooo、siooisi、tau0529

配点 400 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

人間は、NN匹のねこに遭遇しました。

ねこ11からNNまで順番に11回なでます。

ここで、ねこ界の序列に由来する特殊ルールがあります。

ねこkk (k≥2)(k\ge 2)を11回撫でるとき、ねこk−1k-1をk−1k-1回 追加で撫でる責務が発生します。ここで、ねこaaとねこbbを撫でる責務があるとき、ねこmin⁡(a,b)\min(a, b)の責務が優先されます。

人間は合計ねこを何回撫でますか?mod  998244353\mod{998244353}で求めて下さい。

制約

  • 1≤N≤1071 \leq N \leq 10^7
  • 入力される値はすべて整数にゃ

入力

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

NN

出力

一行で答えを出力してください。

サンプル 1

入力

1

出力

1

サンプル 2

入力

10

出力

1112083

手が擦り切れました...

サンプル 3

入力

10000000

出力

278370446

参加受付は終了しました。