Given integers $n$ and $k$, find the number of distinct undirected connected graphs with $n$ nodes that satisfy the following conditions:

• The graph has no self-loops, and there is at most one edge between any two nodes.
• All edge weights are integers in the range $[1, k]$.
• For every edge in the graph, there exists at least one minimum spanning tree that contains this edge.

Two graphs are considered different if and only if there exists a pair of nodes $(u, v)$ such that one graph has an edge between $u$ and $v$ while the other does not, or if the edge weights between $u$ and $v$ are different in the two graphs.

Calculate the number of such graphs, modulo $998244353$.

Input

The input consists of a single test case.

The first line contains two positive integers $n$ and $k$ ($1 \le n \le 5 \times 10^4, 1 \le k \le 10$).

Output

Output a single integer representing the answer modulo $998244353$.

Examples

Input 1

3 1

Output 1

4

Input 2

4 2

Output 2

377

Input 3

235 7

Output 3

928998036