1255: LOJ552 -「LibreOJ Round #8」MIN&MAX I
[Creator : ]
Description
对于一个 $n$ 阶排列 $p$，我们建立一张无向简单图 $G(p)$，有 $n$ 个节点，标号从 $1$ 到 $n$，每个点向左右两侧最近的比它大的点以及比它小的点连边。
形式化地，在 $G(p)$ 中，$\forall u<v$，边 $(u,v)$ 存在当且仅当以下四个条件至少一个成立：
形式化地，在 $G(p)$ 中，$\forall u<v$，边 $(u,v)$ 存在当且仅当以下四个条件至少一个成立：
- $p_u<p_v$，且不存在 $u<i<v$ 满足 $p_u<p_i$；
- $p_u>p_v$，且不存在 $u<i<v$ 满足 $p_u>p_i$；
- $p_u<p_v$，且不存在 $u<i<v$ 满足 $p_i<p_v$；
- $p_u>p_v$，且不存在 $u<i<v$ 满足 $p_i>p_v$。
Input
一行一个正整数 $n$。
The only line contains a positive integer $n$ which means the order of the permutation.
Output
一行一个整数 $\mathrm{ans}$ 表示答案。
Output only one line,which contains an integer $\mathrm{ans}$ which means the expected number of the $3$-cycles in $G(p)$ modulo $998244353$.
Constraints
对于所有数据，$1\le n<998244353$。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| Subtask # | 分值（百分比） | $n$ |
|---|---|---|
| 1 | $15$ | $\le 10$ |
| 2 | $20$ | $\le 100$ |
| 3 | $40$ | $\le 10^6$ |
| 4 | $15$ | $\ge 998000000$ |
Sample 1 Input
3
Sample 1 Output
665496236
在所有 $n!$ 种排列中共有 $4$ 个三元简单环 (\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\}$ 各一个)，所以答案为 $\frac{4}{3!}=\frac{2}{3}$，即 $2×3^{−1}(\bmod 998244353)=665496236$。
Sample 2 Input
91
Sample 2 Output
116578319