Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

graph matchings

math

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Star MST

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIn this problem, we will consider complete undirected graphs consisting of $$$n$$$ vertices with weighted edges. The weight of each edge is an integer from $$$1$$$ to $$$k$$$.

An undirected graph is considered beautiful if the sum of weights of all edges incident to vertex $$$1$$$ is equal to the weight of MST in the graph. MST is the minimum spanning tree — a tree consisting of $$$n-1$$$ edges of the graph, which connects all $$$n$$$ vertices and has the minimum sum of weights among all such trees; the weight of MST is the sum of weights of all edges in it.

Calculate the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

Input

The only line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 250$$$; $$$1 \le k \le 250$$$).

Output

Print one integer — the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

Examples

Input

3 2

Output

5

Input

4 4

Output

571

Input

6 9

Output

310640163

Input

42 13

Output

136246935

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 09:33:32 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|