题目描述

对于一个 $n$ 阶排列 $p$，我们建立一张无向简单图 $G(p)$，有 $n$ 个节点，标号从 $1$ 到 $n$，每个点向左右两侧最近的比它大的点以及比它小的点连边。
形式化地，在 $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$。

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

输入格式

一行一个正整数 $n$。

输出格式

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

3

665496236

91

116578319

3

665496236

91

116578319

数据范围与提示

对于所有数据，$1\le n<998244353$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：