You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Great Sequences

Problem Statement

Farmer John's farm is home to $N$ $(1≤N≤30)$ cows, each identified by a unique name represented as a positive integer from $1$ to $N$.

John is interested in creating pairs of sequences, each of length $M$ $(1≤M≤10^9)$. Each sequence is built with the cows' names. A pair of sequences, $(S, T) = ((S_1, S_2, \dots , S_M), (T_1, T_2, \dots , T_M))$, earns the title of a 'beautiful pair' if it satisfies the following condition:

• There exists a binary sequence $X = (X_1, X_2, \dots , X_N)$ of length $N$. For this sequence, at every index $i$ from $1$ to $M$, the $S_i^{th}$ element of $X$ is different from the $T_i^{th}$ element of $X$.

With $N^{2M}$ possible pairs of sequences of length $M$ using the cows' names, John is curious about the number of 'beautiful pairs' he can create.

Given the large number of possible sequences, he wants the answer modulo $998244353$.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains two integers $N$ and $M$.

OUTPUT FORMAT (print output to the terminal / stdout):

Output a single integer: the number of "beautiful pairs" of sequences, modulo $998244353$. The sequences should be of length $M$ and consist of positive integers no greater than $N$.

SAMPLE INPUT 1:

3 2

SAMPLE OUTPUT 1:

36

For example, if sequence $A$ is $(1, 2)$, and sequence B is $(2, 3)$, then $(A, B)$ is a beautiful pair of sequences. Indeed, if we set $X$ to be $(0, 1, 0)$, then $X$ is a binary sequence of length $N$ consisting of $0$ and $1$ that satisfies the condition where the $S_i^{th}$ element of $X$ is different from the $T_i^{th}$ element of $X$ for every index $i$ from $1$ to $M$. Thus, $(A, B)$ satisfies the condition of being a beautiful pair of sequences.

There are a total of $36$ beautiful pairs of sequences, so we print this number.

SAMPLE INPUT 2:

20 231104

SAMPLE OUTPUT 2:

966200489

SCORING:

• Inputs 3-7: $1 \leq N, M \leq 4$
• Inputs 8-10: $1 \leq N \leq 4, 1 \leq M \leq 10^7$
• Inputs 11-20: No additional constraints.