← 返回题目列表

AtCoder · abc386_g

G. 许多 MST

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你正整数 N 和 M。考虑一个加权完整图 N 顶点标记自 1 to N,其中每条边的权重是介于 1 和 M,包括在内。有 M^{N(N-1)/2} 这样的图表。对于它们中的每一个,考虑其最小生成树中包含的边的权重之和。这些金额的总数是多少?打印取模结果 998244353.

约束

  • 2 \le N \le 500
  • 1 \le M \le 500
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M

输出

打印答案。


示例输入 1

3 2

示例输出 1

21

这是八个完整的图,具有三个顶点,其中边权重为 1 or 2。每个图的 MST 中的边在下图中以红色突出显示。

这些图的 MST 边的总和为 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