D - Same Descent Set
Editorial
/


Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
(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}
制約
- 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 つが条件を満たします.
入力例 2
3
出力例 2
10
入力例 3
4
出力例 3
88
入力例 4
10
出力例 4
286574791
Score : 1000 points
Problem Statement
Find the number of pairs (P,Q)=((P_1,P_2,\cdots,P_N),(Q_1,Q_2,\cdots,Q_N)) of permutations of (1,2,\cdots,N) that satisfy the following condition, modulo 998244353.
- For every i (1 \leq i \leq N-1), one of the two conditions below holds.
- P_i < P_{i+1} and Q_i < Q_{i+1}.
- P_i > P_{i+1} and Q_i > Q_{i+1}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- All numbers in the input are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
2
Sample Output 1
2
Two pairs, (P,Q)=((1,2),(1,2)) and (P,Q)=((2,1),(2,1)), satisfy the condition.
Sample Input 2
3
Sample Output 2
10
Sample Input 3
4
Sample Output 3
88
Sample Input 4
10
Sample Output 4
286574791