4422. [ICPC2026河南省赛]神经网络图染色

【题目描述】

神经网络结构是模仿生物神经系统构建的计算模型，由输入层、隐藏层和输出层构成，通过调整神经元连接权重实现信息处理，在人工智能、自动控制等领域具有广泛应用。——百度百科

小 C 正在研究一个具有 $n$ 层隐藏层的神经网络图，可以把它视为一个无向图。节点编号如下：

• 输入层：$0$ 号节点；
• 第 $k$ 层隐藏层（$1 \le k \le n$）：$3k-2$、$3k-1$、$3k$ 号节点；
• 输出层：$3n+1$号节点；

连边规则如下：

1. 输入层的 $0$ 号点与第 $1$ 层隐藏层的 $3$ 个节点（$1,2,3$）均有连边。
2. 相邻隐藏层之间，第k层隐藏层和第 $k+1$ 层隐藏层连边规则如下：$3k-2$ 和 $3k+1,3k+2$ 有连边，$3k-1$ 和 $3k+1,3k+3$ 有连边，$3k$ 和 $3k+2,3k+3$ 有连边。
3. 第 $n$ 层隐藏层的 $3$ 个节点（$3n-2,3n-1,3n$）与输出层的 $3n+1$ 号点均有连边。

例如当 $n=4$ 时，图的结构如下：

小 C 打算用 $m$ 种颜色给图中所有节点染色，要求有连边的两个节点颜色不同，求染色方案数对 $998244353$ 取模的结果。

【输入格式】

输入一行两个空格隔开的正整数 $n,m$（$1 \le n \le 10^5,1 \le m \le 1000$），表示隐藏层的层数和可用颜色的数量。

【输出格式】

输出一行一个非负整数，表示染色方案数对 $998244353$ 取模的结果。

【输入样例 1】

1 3

【输出样例 1】

30

【输入样例 2】

4 2

【输出样例 2】

2

【输入样例 3】

2 10

【输出样例 3】

28478970

【输入样例 4】

100000 1000

【输出样例 4】

937751774

【样例说明】

对于样例 1，图像如下所示：

$1,2,3$ 三个节点颜色相同的方案有 $12$ 种，三个节点恰好使用两种颜色的方案有 $18$ 种，不可能有三种颜色。

对于样例 $2$，图像见题干。合法方案有 $2$ 种。

【来源】

ICPC 2026 河南省赛。