Problem Background

A new perspective without prejudice towards everything — Insight.

"Insight Light" Kay Ish De Blood, is a subtraction thief, also a chaos knight bearing a dark destiny.

Hidden in Kay's right hand is the Chaos Sword. To unleash its sufficient power without losing control, it requires a specific internal structure. She wants to know how many structures meet the conditions. To facilitate your calculations, she has transformed the problem into the following form:

Problem Description

Update during the competition: The typo in the problem statement has been corrected to: adjacent pairs of points have different colors.

In an undirected connected graph $G$, there are $n$ black and $n$ white points, and $1$ red point.
All points are distinct, and the graph has $2n$ edges, with all adjacent pairs of points (i.e., pairs directly connected by an edge) having different colors.

For $\text{type}$ equal to $0$ or $1$, calculate the number of graphs $G$ that meet the conditions under different conditions:

• $\text{type}=0$: No additional conditions.
• $\text{type}=1$: For each maximal connected subgraph that does not include the red point, exactly one point must be specially marked (each mark is also distinct).

The answer should be taken modulo $998244353$.

Input and Output Formats

Input Format

Input consists of two integers $n$ and $\text{type}$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

1 1

Sample Output #1

5

Sample Input #2

2 0

Sample Output #2

45

Sample Input #3

2 1

Sample Output #3

149

Sample Input #4

10 0

Sample Output #4

36011666

Sample Input #5

20 1

Sample Output #5

593465999

Sample Input #6

106 1

Sample Output #6

516553582

Notes

Sample #1 Explanation

When $\text{type}=1$, all $5$ valid graphs include:

1. $R-W'-B$
2. $R-W-B'$
3. $R-B'-W$
4. $R-B-W'$
5. $B'-R-W'$

Since $n=1$, we can distinguish white and black points using $B$ and $W$, and $R$ represents the red point. The horizontal bar indicates an edge, and $B'$ and $W'$ represent marked white and black points, respectively.

Note that in the fifth graph, the single $B$ and $W$ are the maximal connected subgraphs not including $R$, and each must have a mark in this unique position.

Sample #2, #3 Explanation

See the attached image, which shows all $45$ possible graphs $G$ for $\text{type}=0$.

For $\text{type}=1$, simply mark each graph to count the answer as $149$.

Sample #4, #5 Explanation

The answers before taking modulo are $116758263583336861101$ and $4159784334433940020473603987503242886367209494283213841$, respectively.

Data Range

This problem uses subtask testing.

Subtask 1 (8 pts): $n \le 4$;
Subtask 2 (10 pts): $n \le 10^3$, $\text{type}=0$;
Subtask 3 (11 pts): $\text{type}=0$;
Subtask 4 (13 pts): $n \le 100$, $\text{type}=1$;
Subtask 5 (14 pts): $n \le 10^3$, $\text{type}=1$;
Subtask 6 (21 pts): $n\le 10^5$, $\text{type}=1$;
Subtask 7 (23 pts): $\text{type}=1$.

For all data, $1\le n \le 10^7$, $\text{type}\in \{ 0,1\}$.

Hints

For such problems, you might think of finding the answer on OEIS. However, I must remind you that directly searching for the answer sequence will yield no results. Nevertheless, for small data ranges, it is still possible to preprocess the answer sequence.

The image link appears to be broken (?), original link address: https://i.niupic.com/images/2024/04/05/huyP.png

见题面 Input 部分

见题面 Output 部分