← 返回题目列表

AtCoder · abc327_g

G. 许多好的元组问题

中文机器翻译题面 查看原题

分数: 650 点

问题陈述

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

一对长度序列 M 最多由正整数组成 N, (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)),据说 是一对很好的序列 当 (S, T) 满足以下条件。

  • 存在一个序列 X = (X_1, X_2, \dots, X_N) 长度 N 组成 0 和 1 满足以下条件:
    • X_{S_i} \neq X_{T_i} 对于每个 i=1, 2, \dots, M.

其中 N^{2M} 可能的长度序列对 M 最多由正整数组成 N, (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)),求模数 998244353,那些是好的序列对。

约束

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

输入

输入由标准输入按以下格式给出:

N M

输出

打印数字,模数 998244353,长度序列对 M 最多由正整数组成 N 是很好的序列对。


示例输入 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