洞察（Insight）

看待万物毫无偏见的新视角 —— 洞察。 **** 「洞察之光」凯伊·雅思·德·布拉德，是减法盗贼，也是背负黑暗命运的混沌骑士。 凯伊的右手内隐藏着混沌之剑，为了使其发挥出足够的力量又不至于失控，需要满足特定的内部结构。她想知道有多少种符合条件的结构，为了方便你的计算，她把问题转化为如下形式：

赛时更新：题面中的笔误已修改为：相邻点对颜色**互不相同**。 **** 在一个**无向连通图** $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://oeis.org/) 上寻找答案。但我要提醒你的是，直接搜索答案数列不会找到任何结果。然而，对于小数据范围，仍然可以提前处理出答案数列。 图片链接似乎已损坏（？），原链接地址：https://i.niupic.com/images/2024/04/05/huyP.png