好的二元组计数

题目描述

本题中“好的序列对”的定义与 D 题相同。

由不超过 $N$ 的正整数组成、长度为 $M$ 的序列对 $(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$，当 $(S, T)$ 满足以下条件时，被称为好的序列对。

存在一个由 0 和 1 组成、长度为 $N$ 的序列 $X = (X_1, X_2, \dots, X_N)$，满足以下条件：

对每个 $i=1, 2, \dots, M$，有 $X_{S_i} \neq X_{T_i}$。

在由不超过 $N$ 的正整数组成、长度为 $M$ 的所有 $N^{2M}$ 种序列对 $(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$ 中，求其中是好的序列对的个数，模 $998244353$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$

输出格式

输出由不超过 $N$ 的正整数组成、长度为 $M$ 的序列对中是好的序列对的个数模 $998244353$ 的值。

样例

3 2

36

例如，若 $A=(1,2), B=(2,3)$，则 $(A, B)$ 是好的序列对。事实上，若取 $X=(0,1,0)$，则 $X$ 是长度为 $N$、由 0 和 1 组成的序列，满足 $X_{A_1} \neq X_{B_1}$ 和 $X_{A_2} \neq X_{B_2}$。因此 $(A, B)$ 满足好的序列对的条件。

好的序列对总共有 $36$ 个，因此输出这个数。

3 3

168

12 34

539029838

20 231104

966200489

数据范围

• $1 \le N \le 30$
• $1 \le M \le 10^9$
• $N$、$M$ 均为整数。