E. Слабая подпоследовательность
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Петя очень любит строки. Недавно мама подарила ему ваучер на покупку строки в местном магазине. Можно считать, что в магазине присутствуют все возможные строки над алфавитом фиксированного размера. Размер алфавита равен 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».

Входные данные

В первой строке записано два целых числа k (1 ≤ k ≤ 106) и w (2 ≤ w ≤ 109) — размер алфавита и требуемая длина максимальной подстроки, являющейся также слабой подпоследовательностью, соответственно.

Выходные данные

Выведите одно число — количество строк, которые доступны маленькому Пете для покупки по ваучеру, по модулю 1000000007 (109 + 7). Если таких строк бесконечно много — выведите «-1» (без кавычек).

Примеры
Входные данные
2 2
Выходные данные
10
Входные данные
3 5
Выходные данные
1593
Входные данные
2 139
Выходные данные
717248223
Примечание

В первом примере по ваучеру доступны следующие строки: aaa, aab, abab, abb, abba, baa, baab, baba, bba, bbb.