AT_pakencamp_2022_day2_b Grades

在"パ研学園"中，每个学年有 $N$ 个学期，编号为 $1, 2, \ldots, N$。每个学期都会有成绩，成绩用 $1$ 到 $N$ 之间的整数表示。 有一天，作为"パ研学園"的学生的你，在年末查看了自己每个学期的成绩表。这时，你注意到了以下现象。设第 $i$ 学期的成绩为 $G_i$。 - $G$ 是长度为 $N$ 的一个排列。 - 从第 $2$ 学期起，存在某些学期使得成绩比前一学期下降，并且这些学期在一个连续的区间内。 请你计算满足上述条件的成绩序列 $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$ 分) 无额外限制 ## 样例解释 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$。 该输入满足所有子任务的限制。 ## 样例解释 2 该输入满足子任务 $2, 3, 4, 5$ 的限制。 ## 样例解释 3 该输入满足子任务 $3, 4, 5$ 的限制。 ## 样例解释 4 该输入满足子任务 $4, 5$ 的限制。 ## 样例解释 5 该输入满足子任务 $5$ 的限制。 ## 范围与约定 - 输入均为整数 - $2 \leq N \leq 10^{18}$ 由 ChatGPT 5 翻译