← 返回题目列表

Codeforces · 135/E

E. 弱子序列

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

小Petya非常喜欢弦乐。最近,他收到了一张代金券,可以从母亲那里购买一根绳子作为礼物。绳子可以在当地商店购买。人们可以认为商店里有固定大小的字母表上的各种字符串。字母表的大小等于k。然而,凭证有一个字符串类型的限制:具体来说,如果字符串的最长子串(同时也是其弱子序列(参见下面给出的定义))的长度等于w,则凭证可以用于购买字符串s。

长度为 n 的字符串 a 被认为是长度为 m 的字符串 s 的弱子序列,如果存在这样一组索引 1 ≤ i1 < i2 < ... < in ≤ m,且具有以下两个性质:

- 对于从 1 到 n 的所有 k,ak = sik;
- 至少存在一个这样的 k (1 ≤ k < n),其中 ik + 1 – ik > 1。

Petya 感兴趣的是他可以在商店购买多少种不同的琴弦。由于字符串的数量可能非常大,请对 1000000007 (109 + 7) 求模。如果有无限多个这样的字符串,则打印“-1”。

输入

第一行包含两个整数 k (1 ≤ k ≤ 106) 和 w (2 ≤ w ≤ 109) — 相应的字母表大小和最大子串(也是弱子序列)所需的长度。

输出

打印一个数字 — Petya 可以使用优惠券购买的字符串数量,模 1000000007 (109 + 7)。如果有无限多个这样的字符串,则打印“-1”(不带引号)。

示例

输入 #1

2 2

输出 #1

10

输入 #2

3 5

输出 #2

1593

输入 #3

2 139

输出 #3

717248223

注意

在第一个样本中,Petya 可以购买以下字符串:aaa、aab、abab、abb、abba、baa、baab、baba、bba、bbb。