← 返回题目列表

AtCoder · agc060_d

D. 相同的下降设置

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

查找对的数量 (P,Q)=((P_1,P_2,\cdots,P_N),(Q_1,Q_2,\cdots,Q_N)) 的排列 (1,2,\cdots,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}.

约束

  • 2 \leq N \leq 2 \times 10^5
  • 输入中的所有数字均为整数。

输入

输入由标准输入按以下格式给出:

N

输出

打印答案。


示例输入 1

2

示例输出 1

2

两对, (P,Q)=((1,2),(1,2)) 和 (P,Q)=((2,1),(2,1)),满足条件。


示例输入 2

3

示例输出 2

10

示例输入 3

4

示例输出 3

88

示例输入 4

10

示例输出 4

286574791