传统题 1000ms 512MiB

计数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小可爱做了一个梦,梦里从左到右有 nn 个糖果,每种糖果有一个在 [1,m][1, m] 之间的颜色。小可爱每次会选择两个颜色相同的糖果,把它们以及它们之间的所有糖果吃掉。小可爱记得对于梦里的糖果序列,存在一种方法把所有糖果吃完。小可爱醒来后忘记了梦中的糖果序列是什么,你能帮她求求在所有 mnm^n 个可能的糖果序列中,有多少个糖果序列可能在小可爱梦中(存在一种全部吃完的方式)吗?由于结果很大,你只要求出它除以 109+710^9 + 7 得到的余数即可。

输入格式

一行两个正整数 nnmm,含义与题面中相同。

输出格式

一行一个正整数,表示答案除以 109+710^9 + 7 得到的余数。

样例

输入

3 2

输出

4

解释

44 个合法的糖果序列:[1,1,1][1,2,1][2,1,2][2,2,2][1, 1, 1],[1, 2, 1],[2, 1, 2],[2, 2, 2]

数据规模与约定

  • 对于 10% 的数据,1n61m41 ≤ n ≤ 6,1 ≤ m ≤ 4
  • 对于 20% 的数据,1n61m10001 ≤ n ≤ 6,1 ≤ m ≤ 1000
  • 对于另 30% 的数据,1n501m21 ≤ n ≤ 50,1 ≤ m ≤ 2
  • 对于 70% 的数据,1n1001m1001 ≤ n ≤ 100,1 ≤ m ≤ 100
  • 对于 80% 的数据,1n10001m10001 ≤ n ≤ 1000,1 ≤ m ≤ 1000
  • 对于 100% 的数据,1n30001m1091 ≤ n ≤ 3000,1 ≤ m ≤ 10^9

五一算法挑战赛

未参加
状态
已结束
规则
IOI
题目
8
开始于
2025-5-5 8:00
结束于
2025-5-5 10:00
持续时间
2 小时
主持人
参赛人数
10