B - Grades 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

パ研学園では各年度に N 個の学期があり、 1, 2, \ldots, N の番号が付いています。各学期ごとに成績が付き、成績は 1 から N までの整数値で表されます。

さて、パ研学園の生徒であるあなたは、一年の最後に自分の各学期の成績表を眺めていました。すると、次のことに気が付きました。ここで i 番目の学期の成績を G_i とします。

  • G は長さ N の順列である。
  • 2 学期以降について、前の学期より成績が下がっている学期が存在し、それらは連続する 1 つの区間になっている。

このとき、これらの条件を満たす成績 G_1, G_2, \ldots, G_N の個数を求めて下さい。ただし、答えはとても大きくなることがあるので、答えを 998244353 で割った余りを出力してください。

制約

  • 入力は全て整数
  • 2 \leq N \leq 10^{18}

小課題

  1. (50 点) N \leq 8
  2. (50 点) N \leq 15
  3. (200 点) N \leq 3000
  4. (100 点) N \leq 10^6
  5. (100 点) 追加の制約はない

入力

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

N

出力

答えを 998244353 で割った余りを出力せよ。


入力例 1

4

出力例 1

18

順列である G のうち、 G_1 < G_2 < G_3 < G_4 の時と G_1 > G_2 < G_3 > G_4 の時のみが条件を満たしません。

そのような G(1, 2, 3, 4), (2, 1, 4, 3), (3, 1, 4, 2), (3, 2, 4, 1), (4, 1, 3, 2), (4, 2, 3, 1)6 つあります。長さ 4 の順列は 24 個あるため、答えは 18 になります。

この入力は全ての小課題の制約を満たします。


入力例 2

13

出力例 2

398574

この入力は小課題 2, 3, 4, 5 の制約を満たします。


入力例 3

2947

出力例 3

663703367

この入力は小課題 3, 4, 5 の制約を満たします。


入力例 4

999999

出力例 4

946508973

この入力は小課題 4, 5 の制約を満たします。


入力例 5

1000000000000000000

出力例 5

856673235

この入力は小課題 5 の制約を満たします。