AT_pakencamp_2022_day2_b Grades

パ研学園では各年度に $ N $ 個の学期があり、 $ 1, 2, \ldots, N $ の番号が付いています。各学期ごとに成績が付き、成績は $ 1 $ から $ N $ までの整数値で表されます。 さて、パ研学園の生徒であるあなたは、一年の最後に自分の各学期の成績表を眺めていました。すると、次のことに気が付きました。ここで $ i $ 番目の学期の成績を $ G_i $ とします。 - $ G $ は長さ $ N $ の順列である。 - $ 2 $ 学期以降について、前の学期より成績が下がっている学期が存在し、それらは連続する $ 1 $ つの区間になっている。 このとき、これらの条件を満たす成績 $ G_1, G_2, \ldots, G_N $ の個数を求めて下さい。ただし、答えはとても大きくなることがあるので、答えを $ 998244353 $ で割った余りを出力してください。

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

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

### 小課題 1. ( $ 50 $ 点) $ N \leq 8 $ 2. ( $ 50 $ 点) $ N \leq 15 $ 3. ( $ 200 $ 点) $ N \leq 3000 $ 4. ( $ 100 $ 点) $ N \leq 10^6 $ 5. ( $ 100 $ 点) 追加の制約はない ### Sample Explanation 1 順列である $ 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 $ になります。 この入力は全ての小課題の制約を満たします。 ### Sample Explanation 2 この入力は小課題 $ 2, 3, 4, 5 $ の制約を満たします。 ### Sample Explanation 3 この入力は小課題 $ 3, 4, 5 $ の制約を満たします。 ### Sample Explanation 4 この入力は小課題 $ 4, 5 $ の制約を満たします。 ### Sample Explanation 5 この入力は小課題 $ 5 $ の制約を満たします。 ### Constraints - 入力は全て整数 - $ 2 \leq N \leq 10^{18} $