Weak Subsequence

## 题目描述 小$Petya$非常喜欢字符串。最近他收到了他妈妈送给他的一份礼物：一张购买字符串的优惠券。字符串可以在当地的商店买到。你可以认为商店里有所有长度为$k$的、由字母组成的字符串。然而，这张优惠券对字符串有一些限制：优惠券能用于购买字符串$s$，当且仅当$s$的子串中，最长“弱字串”（下面给出了“弱字串的定义”）的长度为$w$. 长度为$n$的字符串$a$的长度为$m$的子串$s$被称作“弱字串”，当且仅当存在一系列数$1\leq i_1 < i_2 <...<i_n\leq m$，使得下列条件成立： · $\forall k\in[1,n]$， $a_{k}=s_{ik}$； · 存在至少一个$k\in [1,n]$，使得$i_{k+1}-i_{k}>1$. $Petya$对他能用优惠券购买商店中多少种不同的字符串这个问题产生了兴趣。由于答案可能很大，请输出结果对$10^{9}+7$取模的结果。如果不存在这样的字符串，请输出$-1$. ## 输入格式 输入文件的第一行包含两个整数$k(1<=k<=10^{6})$和$w(2<=w<=10^{9})$——字母表的大小和子串长度，也是“弱字串”的长度. ## 输出格式 输出一个整数——$Petya$能用优惠券购买的字串数，对$10^9+7$取模；若不存在这样的字串，输出$-1$. 翻译 By @若如初见

Little Petya very much likes strings. Recently he has received a voucher to purchase a string as a gift from his mother. The string can be bought in the local shop. One can consider that the shop has all sorts of strings over the alphabet of fixed size. The size of the alphabet is equal to $ k $ . However, the voucher has a string type limitation: specifically, the voucher can be used to purchase string $ s $ if the length of string's longest substring that is also its weak subsequence (see the definition given below) equals $ w $ . String $ a $ with the length of $ n $ is considered the weak subsequence of the string $ s $ with the length of $ m $ , if there exists such a set of indexes $ 1<=i_{1}&lt;i_{2}&lt;...&lt;i_{n}<=m $ , that has the following two properties: - $ a_{k}=s_{ik} $ for all $ k $ from $ 1 $ to $ n $ ; - there exists at least one such $ k $ ( $ 1<=k&lt;n $ ), for which $ i_{k+1}–i_{k}&gt;1 $ . Petya got interested how many different strings are available for him to purchase in the shop. As the number of strings can be very large, please find it modulo $ 1000000007 $ ( $ 10^{9}+7 $ ). If there are infinitely many such strings, print "-1".

The first line contains two integers $ k $ ( $ 1<=k<=10^{6} $ ) and $ w $ ( $ 2<=w<=10^{9} $ ) — the alphabet size and the required length of the maximum substring that also is the weak subsequence, correspondingly.

Print a single number — the number of strings Petya can buy using the voucher, modulo $ 1000000007 $ ( $ 10^{9}+7 $ ). If there are infinitely many such strings, print "-1" (without the quotes).

2 2

10

3 5

1593

2 139

717248223

In the first sample Petya can buy the following strings: aaa, aab, abab, abb, abba, baa, baab, baba, bba, bbb.