Contest Duration: - (local time) (180 minutes) Back to Home
D - Same Descent Set /

Time Limit: 6 sec / Memory Limit: 1024 MB

問題文

(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


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