103276: [Atcoder]ABC327 G - Many Good Tuple Problems

Problem Statement

The definition of a good pair of sequences in this problem is the same as in Problem D.

A pair of sequences of length $M$ consisting of positive integers at most $N$, $(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$, is said to be a good pair of sequences when $(S, T)$ satisfies the following condition.

• There exists a sequence $X = (X_1, X_2, \dots, X_N)$ of length $N$ consisting of $0$ and $1$ that satisfies the following condition:
  • $X_{S_i} \neq X_{T_i}$ for each $i=1, 2, \dots, M$.

Among the $N^{2M}$ possible pairs of sequences of length $M$ consisting of positive integers at most $N$, $(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$, find the number, modulo $998244353$, of those that are good pairs of sequences.

Constraints

• $1 \leq N \leq 30$
• $1 \leq M \leq 10^9$
• $N$ and $M$ are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

Output

Print the number, modulo $998244353$, of pairs of sequences of length $M$ consisting of positive integers at most $N$ that are good pairs of sequences.

Sample Input 1

3 2

Sample Output 1

36

For example, if $A=(1,2), B=(2,3)$, then $(A, B)$ is a good pair of sequences. Indeed, if we set $X=(0,1,0)$, then $X$ is a sequence of length $N$ consisting of $0$ and $1$ that satisfies $X_{A_1} \neq X_{B_1}$ and $X_{A_2} \neq X_{B_2}$. Thus, $(A, B)$ satisfies the condition of being a good pair of sequences.
There are a total of $36$ good pairs of sequences, so print this number.

Sample Input 2

3 3

Sample Output 2

168

Sample Input 3

12 34

Sample Output 3

539029838

Sample Input 4

20 231104

Sample Output 4

966200489

问题描述

本题中，好序列对的定义与问题D中的定义相同。

长度为$M$，由正整数构成的两个序列$(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$，当$(S, T)$满足以下条件时，被称为< strong>好序列对：

• 存在一个长度为$N$的由$0$和$1$构成的序列$X = (X_1, X_2, \dots, X_N)$，满足以下条件：
  • 对于每个$i=1, 2, \dots, M$，有$X_{S_i} \neq X_{T_i}$。

在长度为$M$的两个序列$(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$中，找出由正整数构成的$N^{2M}$个可能的对，其中$(A, B)$是好序列对的个数，对结果取模$998244353$。

限制条件

• $1 \leq N \leq 30$
• $1 \leq M \leq 10^9$
• $N$和$M$是整数。

输入

输入以标准输入的形式给出，如下所示：

$N$ $M$

输出

输出长度为$M$的两个序列，由正整数构成的$N^{2M}$个可能的对中，是好序列对的个数，对结果取模$998244353$。

样例输入1

3 2

样例输出1

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$个好序列对，所以打印这个数。

样例输入2

3 3

样例输出2

168

样例输入3

12 34

样例输出3

539029838

样例输入4

20 231104

样例输出4

966200489