# #552. 「LibreOJ Round #8」MIN&MAX I

#### 题目描述

• $p_u，且不存在 $u 满足 $p_u
• $p_u>p_v$，且不存在 $u 满足 $p_u>p_i$
• $p_u，且不存在 $u 满足 $p_i
• $p_u>p_v$，且不存在 $u 满足 $p_i>p_v$

For an $n$-order permutation $p$, we set up an undirected simple graph $G(p)$ with $n$ vertices numbered from $1$ to $n$. We create an edge between each vertice $i$ and the nearest vertices in each side which correspond a greater (or less) $p$ value than $p_i$.
Formally,in this graph, $\forall u, the edge $(u, v)$ exists iff at least one of the following four conditions hold:

• $p_u, and no $u exists such that $p_u;
• $p_u>p_v$, and no $u exists such that $p_u>p_i$;
• $p_u, and no $u exists such that $p_i;
• $p_u>p_v$, and no $u exists such that $p_i>p_v$.

Now we randomly choose a permutation $p$ from all $n$-order permutations. Your task is to calculate the expected number of the $3$-cycles in $G(p)$. You only need to output the answer modulo $998244353$.

#### 输入格式

The only line contains a positive integer $n$ which means the order of the permutation.

#### 输出格式

Output only one line,which contains an integer $\mathrm{ans}$ which means the expected number of the $3$-cycles in $G(p)$ modulo $998244353$.

#### 样例输入 1

3

#### 样例输出 1

665496236

#### 样例输入 2

91

#### 样例输出 2

116578319

#### Sample Input 1

3

#### Sample Output 1

665496236

#### Sample Explanation 1

It is easy to count that there are four $3$-cycles in total from the $3!$ permutations(each of $\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\}$ has one). So answer is $\frac{4}{3!}=\frac{2}{3}$,that is, $2\times 3^{-1} \pmod{998244353}=665496236$.

#### Sample Input 2

91

#### Sample Output 2

116578319

#### 数据范围与提示

Subtask # 分值（百分比） $n$
$1$ $15$ $\le 10$
$2$ $20$ $\le 100$
$3$ $40$ $\le 10^6$
$4$ $15$ $\ge 998000000$
$5$ $10$ -

For all test cases, $1\le n<998244353$.

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):

Subtask # Score (percentage) $n$
$1$ $15$ $\le 10$
$2$ $20$ $\le 100$
$3$ $40$ $\le 10^6$
$4$ $15$ $\ge 998000000$
$5$ $10$ -