Problem Description

Makoto-kun came up with the following problem.

Input Format

The input is given from the standard input in the following format.

$ N $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

2

Sample Output #1

8

Sample Input #2

4

Sample Output #2

4944

Sample Input #3

2021

Sample Output #3

383310824

Sample Input #4

100000

Sample Output #4

143469183

Notes/Hints

An Interval Scheduling Problem

You are given $ N $ intervals $ [L_i, R_i] $. Find the maximum number of intervals that can be selected such that no two selected intervals overlap.

Constraints

• The sequences $ L $ and $ R $ contain each integer from $ 1 $ to $ 2N $ exactly once.
• $L_i\ (\ 1\ \leq\ i\ \leq\ N)$

This problem was too typical, so Teruo-kun, who loves counting, modified the problem as follows.

Interval Scheduling Problems

Given an integer $ N $, output the sum of the solutions for all valid inputs that satisfy the constraints of An Interval Scheduling Problem, modulo $ 998244353 $.

Solve Interval Scheduling Problems.

Constraints

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$

Partial Points

This problem has multiple partial points.

• $1\ \le\ N\ \le\ 50$: $ 10 $ points will be awarded for correct answers.
• $1\ \le\ N\ \le\ 3000$: $ 30 $ points will be awarded for correct answers.

Sample Explanation 1

The possible inputs for An Interval Scheduling Problem are as follows:
- $L=(1,2),\ R=(3,4)$
- $L=(1,2),\ R=(4,3)$
- $L=(1,3),\ R=(2,4)$
- $L=(2,1),\ R=(3,4)$
- $L=(2,1),\ R=(4,3)$
- $L=(3,1),\ R=(4,2)$

The answers for An Interval Scheduling Problem for these inputs are $ 1, 1, 2, 1, 1, 2 $, respectively. Therefore, the answer for Interval Scheduling Problems is $ 1 + 1 + 2 + 1 + 1 + 2 $ modulo $ 998244353 $, which is $ 8 $.

Sample Explanation 2

This test case is included in the partial points worth $ 10 $ points.

Sample Explanation 3

This test case is included in the partial points worth $ 30 $ points.

Sample Explanation 4

This test case is not included in the partial points.

见题面 Input 部分

见题面 Output 部分