题目背景

看待万物毫无偏见的新视角 —— 洞察

---

「洞察之光」凯伊·雅思·德·布拉德，是减法盗贼，也是背负黑暗命运的混沌骑士。

凯伊的右手内隐藏着混沌之剑，为了使其发挥出足够的力量又不至于失控，需要满足特定的内部结构。她想知道有多少种符合条件的结构，为了方便你的计算，她把问题转化为如下形式：

题目描述

赛时更新：题面中的笔误已修改为：相邻点对颜色互不相同。

---

在一个无向连通图 $G$ 中，有黑色和白色的点各 $n$ 个，红色的点 $1$ 个。
所有点之间互不相同，图中有 $2n$ 条边，且所有相邻点对（也就是有边直接相连的点对）的颜色也互不相同。

对于 $\text{type}$ 等于 $0$ 或 $1$，分别在不同条件下计算符合条件的图 $G$ 有多少个：

• $\text{type}=0$：无附加条件。
• $\text{type}=1$：对于每个不包含红色点的极大连通子图，都要对恰好一个点做特殊标记（每个标记也都是不同的）。

答案对 $998244353$ 取模。

输入格式

输入一行两个整数 $n$ 和 $\text{type}$。

输出格式

输出一行一个整数表示答案。

1 1

5

2 0

45

2 1

149

10 0

36011666

20 1

593465999

106 1

516553582

提示

【样例 $1$ 解释】
此时 $\text{type}=1$，所有 $5$ 种合法的图包括：

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

由于 $n=1$，可以仅用 $B$ 和 $W$ 来区分白点和黑点，$R$ 表示红点。中间的横杠表示连边，$B'$ 和 $W'$ 分别表示有标记的白点和黑点。

注意，由于第 $5$ 个图中，单个的 $B$ 和 $W$ 就是不包含 $R$ 的极大连通子图，必须各有一个标记在这唯一的位置上。

【样例 $2,3$ 解释】

见附件图片，其中展示了 $\text{type}=0$ 时全部的 $45$ 种可能的图 $G$。

对于 $\text{type}=1$ 的情况，只需要对每个图的基础上做标记，就可以数出答案为 $149$。

【样例 $4,5$ 解释】

取模前的答案分别为 $116758263583336861101$ 和 $4159784334433940020473603987503242886367209494283213841$。

【数据范围】

本题采用捆绑测试。

Subtask 1（8 pts）：$n \le4$；
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$。

对于全部的数据，$1\le n \le 10^7$，$\text{type}\in \{ 0,1\}$。

【提示】
对于这类题目，你或许会想从 OEIS 上寻找答案。但我要提醒你的是，直接搜索答案数列不会找到任何结果。然而，对于小数据范围，仍然可以提前处理出答案数列。

图片链接似乎已损坏（？），原链接地址：https://i.niupic.com/images/2024/04/05/huyP.png