A22644.Mivik 写书

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Mivik 想当大作家。Mivik 的键盘上有 mm 个不同的按键,对应着 mm 个不同的字符。由于 Mivik 不会写文章,所以他只好等概率随机乱按了 nn 个键,打出了一篇文章。

Mivik 定义一篇文章的复杂度是这篇文章所有非空本质不同子串的数目。我们认为两个字符串本质不同当且仅当它们的长度不同或者它们有任意一位上的字符不同。例如,文章 abaa 的复杂度是 8,因为它一共有 ababbaaaababaaabaa 这 8 个非空的本质不同子串。

Mivik 现在想知道,这篇文章期望的复杂度是多少。由于 Mivik 不喜欢奇形怪状的小数,你只需要输出期望的复杂度对 109+710^9+7 取模后的值。

输入格式

一行两个整数 nnmm,意义见题目描述。

输出格式

一行一个整数,代表答案对 109+710^9+7 取模后的值。

输入输出样例

  • 输入#1

    2 2

    输出#1

    500000006
  • 输入#2

    3 3

    输出#2

    5
  • 输入#3

    3 4

    输出#3

    250000007

说明/提示

样例解释

样例一:假设键盘上的字符分别为 ab,那么可能打出来的文章一共有 aaabbabb 四种,它们的复杂度分别为 2、3、3、2,因此答案为 2+3+3+24=52\frac{2+3+3+2}{4}=\frac{5}{2},对 109+710^9+7 取模后得到 500000006。

数据范围

对于全部数据,有 1n201\le n\le 201m51061\le m\le 5\cdot 10^6

首页