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