問題文

パ研学園では各年度に 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 点) 追加の制約はない

入力例 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 の制約を満たします。