/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N,M が与えられます。頂点に 1 から N までの番号がつけられている N 頂点の重み付き完全グラフであって各辺の重みが 1 以上 M 以下の整数であるようなものは M^{N(N-1)/2} 通りありますが、それぞれについて最小全域木に含まれる辺の重みの和を求めたとき、それらの総和はいくつになりますか？総和を 998244353 で割った余りを出力してください。
制約
- 2\leq N\leq 500
- 1\leq M\leq 500
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
21
辺の重みが 1 または 2 である 3 頂点の重み付き完全グラフは以下の 8 つあります。それぞれの完全グラフについて、最小全域木に含まれる辺は赤色で塗られています。
それぞれの完全グラフの最小全域木に含まれる辺の重みの和は 2,2,2,3,2,3,3,4 であるため、求める答えは 2+2+2+3+2+3+3+4=21 です。
入力例 2
2 100
出力例 2
5050
入力例 3
20 24
出力例 3
707081320
Score : 600 points
Problem Statement
You are given positive integers N and M. Consider a weighted complete graph with N vertices labeled from 1 to N, where the weight of each edge is an integer between 1 and M, inclusive. There are M^{N(N-1)/2} such graphs. For each of them, consider the sum of the weights of the edges included in its Minimum Spanning Tree. What is the total of these sums? Print the result modulo 998244353.
Constraints
- 2 \le N \le 500
- 1 \le M \le 500
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
21
Here are eight complete graphs with three vertices where edge weights are 1 or 2. The edges in each graph’s MST are highlighted in red in the figure below.
The sums of the MST edges for these graphs are 2,2,2,3,2,3,3,4, so the total is 2+2+2+3+2+3+3+4=21.
Sample Input 2
2 100
Sample Output 2
5050
Sample Input 3
20 24
Sample Output 3
707081320