{"raw_statement":[{"iden":"background","content":"看待万物毫无偏见的新视角 —— 洞察。\n\n****\n「洞察之光」凯伊·雅思·德·布拉德，是减法盗贼，也是背负黑暗命运的混沌骑士。\n\n凯伊的右手内隐藏着混沌之剑，为了使其发挥出足够的力量又不至于失控，需要满足特定的内部结构。她想知道有多少种符合条件的结构，为了方便你的计算，她把问题转化为如下形式："},{"iden":"statement","content":"赛时更新：题面中的笔误已修改为：相邻点对颜色**互不相同**。\n****\n在一个**无向连通图** $G$ 中，有黑色和白色的点各 $n$ 个，红色的点 $1$ 个。  \n所有点都有标号，图中有 $2n$ 条边，且所有相邻点对（也就是有边直接相连的点对）的颜色也互不相同。\n\n对于 $\\text{type}$ 等于 $0$ 或 $1$，分别在不同条件下计算符合条件的图 $G$ 有多少个：\n\n- $\\text{type}=0$：无附加条件。  \n- $\\text{type}=1$：对于每个**不包含**红色点的极大连通子图，都要对**恰好一个**点做特殊标记（每个标记也都是不同的）。\n\n答案对 $998244353$ 取模。"},{"iden":"input","content":"输入一行两个整数 $n$ 和 $\\text{type}$。\n"},{"iden":"output","content":"输出一行一个整数表示答案。"},{"iden":"note","content":"【样例 $1$ 解释】  \n此时 $\\text{type}=1$，所有 $5$ 种合法的图包括：\n\n1. $R-W'-B$\n2. $R-W-B'$\n3. $R-B'-W$\n4. $R-B-W'$\n5. $B'-R-W'$\n\n由于 $n=1$，可以仅用 $B$ 和 $W$ 来区分白点和黑点，$R$ 表示红点。中间的横杠表示连边，$B'$ 和 $W'$ 分别表示有标记的白点和黑点。\n\n注意，由于第 $5$ 个图中，单个的 $B$ 和 $W$ 就是不包含 $R$ 的极大连通子图，必须各有一个标记在这唯一的位置上。\n\n【样例 $2,3$ 解释】\n\n见附件图片，其中展示了 $\\text{type}=0$ 时全部的 $45$ 种可能的图 $G$。\n\n对于 $\\text{type}=1$ 的情况，只需要对每个图的基础上做标记，就可以数出答案为 $149$。\n\n【样例 $4,5$ 解释】\n\n取模前的答案分别为 $116758263583336861101$ 和 $4159784334433940020473603987503242886367209494283213841$。\n\n【数据范围】\n\n**本题采用捆绑测试。**\n\nSubtask 1（8 pts）：$n \\le4$；     \nSubtask 2（10 pts）：$n \\le 10^3$，$\\text{type}=0$；  \nSubtask 3（11 pts）：$\\text{type}=0$；  \nSubtask 4（13 pts）：$n \\le 100$，$\\text{type}=1$；     \nSubtask 5（14 pts）：$n \\le 10^3$，$\\text{type}=1$；  \nSubtask 6（21 pts）：$n\\le 10^5$，$\\text{type}=1$；  \nSubtask 7（23 pts）：$\\text{type}=1$。\n\n对于全部的数据，$1\\le n \\le 10^7$，$\\text{type}\\in \\{ 0,1\\}$。\n\n【提示】  \n对于这类题目，你或许会想从 [OEIS](https://oeis.org/) 上寻找答案。但我要提醒你的是，直接搜索答案数列不会找到任何结果。然而，对于小数据范围，仍然可以提前处理出答案数列。\n"}],"translated_statement":null,"sample_group":[["1 1","5"],["2 0","45"],["2 1","149"],["10 0","36011666"],["20 1","593465999"],["106 1","516553582"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}