実行時間制限: 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}
小課題
- (50 点) N \leq 8
- (50 点) N \leq 15
- (200 点) N \leq 3000
- (100 点) N \leq 10^6
- (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 の制約を満たします。