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

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

对于一个 nnn 阶排列 ppp,我们建立一张无向简单图 G(p)G(p)G(p),有 nnn 个节点,标号从 111nnn,每个点向左右两侧最近的比它大的点以及比它小的点连边。
形式化地,在 G(p)G(p)G(p) 中,∀u<v\forall u<vu<v,边 (u,v)(u,v)(u,v) 存在当且仅当以下四个条件至少一个成立:

  • pu<pvp_u<p_vpu<pv,且不存在 u<i<vu<i<vu<i<v 满足 pu<pip_u<p_ipu<pi
  • pu>pvp_u>p_vpu>pv,且不存在 u<i<vu<i<vu<i<v 满足 pu>pip_u>p_ipu>pi
  • pu<pvp_u<p_vpu<pv,且不存在 u<i<vu<i<vu<i<v 满足 pi<pvp_i<p_vpi<pv
  • pu>pvp_u>p_vpu>pv,且不存在 u<i<vu<i<vu<i<v 满足 pi>pvp_i>p_vpi>pv

现在在所有的 nnn 阶排列中随机选择一个排列 ppp,请求出 G(p)G(p)G(p) 中三元简单环的期望个数,答案对 998244353998244353998244353 取模。

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

  • pu<pvp_u<p_vpu<pv, and no u<i<vu<i<vu<i<v exists such that pu<pip_u<p_ipu<pi;
  • pu>pvp_u>p_vpu>pv, and no u<i<vu<i<vu<i<v exists such that pu>pip_u>p_ipu>pi;
  • pu<pvp_u<p_vpu<pv, and no u<i<vu<i<vu<i<v exists such that pi<pvp_i<p_vpi<pv;
  • pu>pvp_u>p_vpu>pv, and no u<i<vu<i<vu<i<v exists such that pi>pvp_i>p_vpi>pv.

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

输入格式

一行一个正整数 nnn

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

输出格式

一行一个整数 ans\mathrm{ans}ans 表示答案。

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

样例

样例输入 1

3

样例输出 1

665496236

样例解释 1

在所有 n!n!n! 种排列中共有 444 个三元简单环({1,3,2},{2,3,1},{2,1,3},{3,1,2}\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\}{1,3,2},{2,3,1},{2,1,3},{3,1,2} 各一个),所以答案为 43!=23\frac{4}{3!}=\frac{2}{3}3!4=32,即 2×31(mod998244353)=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 333-cycles in total from the 3!3!3! permutations(each of {1,3,2},{2,3,1},{2,1,3},{3,1,2}\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\}{1,3,2},{2,3,1},{2,1,3},{3,1,2} has one). So answer is 43!=23\frac{4}{3!}=\frac{2}{3}3!4=32,that is, 2×31(mod998244353)=665496236.

Sample Input 2

91

Sample Output 2

116578319

数据范围与提示

对于所有数据,1≤n<9982443531\le n<9982443531n<998244353

详细的数据限制及约定如下(留空表示和上述所有数据的约定相同):

Subtask # 分值(百分比) nnn
111 151515 ≤10\le 1010
222 202020 ≤100\le 100100
333 404040 ≤106\le 10^6106
444 151515 ≥998000000\ge 998000000998000000