Score : $650$ points

问题描述

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

当满足以下条件时，长度为$M$且包含不大于$N$的正整数的两个序列$(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}$。

在所有可能的由不大于$N$的正整数组成的长度为$M$的序列对$(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$中，求出（模$998244353$）满足是好的序列对的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:52:05