AT_abc327_g [ABC327G] Many Good Tuple Problems

题目描述

本题中“良い数列の組”（好数列对）的定义与 D 问题相同。

设 $N$ 为正整数，$M$ 为正整数。对于所有由不超过 $N$ 的正整数组成的长度为 $M$ 的数列对 $(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$，若满足以下条件，则称其为好数列对：

• 存在一个由 $0,1$ 组成的长度为 $N$ 的数列 $X = (X_1, X_2, \dots, X_N)$，使得对于每个 $i=1,2,\dots,M$，都有 $X_{S_i} \neq X_{T_i}$。

所有可能的数列对 $(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$ 的总数为 $N^{2M}$。请计算其中好数列对的数量，并对 $998244353$ 取模后输出。

输入格式

输入从标准输入读取，格式如下：

$N$ $M$

输出格式

输出所有由不超过 $N$ 的正整数组成的长度为 $M$ 的数列对中，好数列对的数量对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3 2

输出 #1

36

输入输出样例 #2

输入 #2

3 3

输出 #2

168

输入输出样例 #3

输入 #3

12 34

输出 #3

539029838

输入输出样例 #4

输入 #4

20 231104

输出 #4

966200489

说明/提示

限制条件

• $1 \leq N \leq 30$
• $1 \leq M \leq 10^9$
• $N, M$ 均为整数

样例解释 1

例如，当 $A=(1,2), B=(2,3)$ 时，$(A,B)$ 是一个好数列对。取 $X=(0,1,0)$，这是一个由 $0,1$ 组成的长度为 $N$ 的数列，且 $X_{A_1} \neq X_{B_1}$ 且 $X_{A_2} \neq X_{B_2}$ 都成立。因此，$(A,B)$ 满足好数列对的条件。所有好数列对共有 $36$ 个，因此输出 $36$。

由 ChatGPT 4.1 翻译