分数: 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