/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
この問題における良い数列の組の定義は 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 の数列の組 (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)) としてあり得るものは N^{2M} 通りありますが、そのような数列の組のうち良い数列の組であるものの個数を 998244353 で割った余りを求めてください。
制約
- 1 \leq N \leq 30
- 1 \leq M \leq 10^9
- N, M は整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
N 以下の正整数からなる長さ M の数列の組のうち、良い数列の組であるものの個数を 998244353 で割った余りを出力せよ。
入力例 1
3 2
出力例 1
36
例えば A=(1,2), B=(2,3) のとき (A, B) は良い数列の組です。X=(0,1,0) とすると、X は 0,1 からなる長さ N の数列で、 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
Score : 650 points
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