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.