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