Background

A new perspective that sees everything without bias — Insight.

"Light of Insight" Kai Yas De Brad is a subtraction thief, and also a chaos knight carrying a dark fate.

Inside Kai’s right hand lies the Sword of Chaos. To make it release enough power without losing control, a specific internal structure must be satisfied. She wants to know how many structures meet the requirements. To make the computation easier, she transforms the problem into the following form.

Problem Description

Update during the contest: A typo in the statement has been fixed to: the colors of every pair of adjacent vertices are all different.

In an undirected connected graph $G$, there are $n$ black vertices, $n$ white vertices, and $1$ red vertex.
All vertices are labeled. The graph has $2n$ edges, and the colors of every pair of adjacent vertices (i.e., every pair of vertices directly connected by an edge) are also all different.

For $\text{type}$ equal to $0$ or $1$, compute how many graphs $G$ satisfy the conditions under different requirements:

• $\text{type}=0$: No additional requirements.
• $\text{type}=1$: For every maximal connected subgraph that does not contain the red vertex, you must place a special mark on exactly one vertex (each mark is also distinct).

Output the answer modulo $998244353$.

Input Format

One line with two integers $n$ and $\text{type}$.

Output Format

One line with one integer, the answer.

1 1

5

2 0

45

2 1

149

10 0

36011666

20 1

593465999

106 1

516553582

Hint

[Sample $1$ Explanation]
Here $\text{type}=1$. All $5$ valid graphs are:

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 use only $B$ and $W$ to distinguish the white vertex and the black vertex. $R$ denotes the red vertex. The dash in the middle denotes an edge. $B'$ and $W'$ denote the marked black vertex and the marked white vertex, respectively.

Note that in the 5th graph, the single $B$ and the single $W$ are maximal connected subgraphs that do not contain $R$, so each must have a mark at this only possible position.

[Sample $2,3$ Explanation]

See the attached images, which show all $45$ possible graphs $G$ when $\text{type}=0$.

For $\text{type}=1$, you only need to add marks on top of each graph, and you can count that the answer is $149$.

[Sample $4,5$ Explanation]

Before taking modulo, the answers are $116758263583336861101$ and $4159784334433940020473603987503242886367209494283213841$, respectively.

[Constraints]

This problem uses bundled testdata.

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 testdata, $1 \le n \le 10^7$, $\text{type} \in \{0,1\}$.

[Hint]
For problems like this, you might want to look for an answer on OEIS. But I want to remind you that directly searching the sequence of answers will not find anything. However, for small constraints, you can still precompute the answer sequence in advance.

Translated by ChatGPT 5