Маленький Петя очень любит строки. Недавно мама подарила ему ваучер на покупку строки в местном магазине. Можно считать, что в магазине присутствуют все возможные строки над алфавитом фиксированного размера. Размер алфавита равен k. Однако этот ваучер имеет ограничение на тип строк, которые можно приобрести при помощи него. А именно, строка s может быть приобретена, если длина самой длинной ее подстроки, которая также является ее слабой подпоследовательностью (см. определение ниже) равна w.
Строка a длины n является слабой подпоследовательностью строки s длины m, если существует такой набор индексов 1 ≤ i1 < i2 < ... < in ≤ m, для которого выполняются два свойства:
- ak = sik для всех k от 1 до n;
- существует хотя бы одно такое k (1 ≤ k < n), для которого ik + 1 – ik > 1.
Пете стало интересно, сколько различных строк доступны ему для покупки в магазине. Так как количество строк может быть очень велико, найдите его по модулю 1000000007 (109 + 7). В случае, если таких строк бесконечно много — выведите «-1».
Выходные данные
Выведите одно число — количество строк, которые доступны маленькому Пете для покупки по ваучеру, по модулю 1000000007 (109 + 7). Если таких строк бесконечно много — выведите «-1» (без кавычек).
Примечание
В первом примере по ваучеру доступны следующие строки: aaa, aab, abab, abb, abba, baa, baab, baba, bba, bbb.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
|
10
|
|
2
|
3 5
|
1593
|
|
3
|
2 139
|
717248223
|