题目描述

求满足以下条件的 $(1,2,\cdots,N)$ 的排列对 $(P,Q)=((P_1,P_2,\cdots,P_N),(Q_1,Q_2,\cdots,Q_N))$ 的个数，并将结果对 $998244353$ 取模。

• 对于所有 $i$（$1 \leq i \leq N-1$），以下任意一个条件成立：
  • $P_i < P_{i+1}$ 且 $Q_i < Q_{i+1}$
  • $P_i > P_{i+1}$ 且 $Q_i > Q_{i+1}$

输入格式

输入以如下格式从标准输入中给出。

$N$

输出格式

请输出答案。

样例 1

输入

2

输出

2

样例 2

输入

3

输出

10

样例 3

输入

4

输出

88

样例 4

输入

10

输出

286574791

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• 输入的数均为整数

样例解释 1

$(P,Q)=((1,2),(1,2))$ 和 $(P,Q)=((2,1),(2,1))$ 这两组满足条件。

由 ChatGPT 4.1 翻译