F. Сумма k-x степеней
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известны следующие формулы , , . Также математиками были получены аналогичные формулы и для больших степеней.

Вам требуется найти значение суммы по модулю 109 + 7 (то есть нужно найти остаток при делении значения суммы на число 109 + 7).

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

В единственной строке находится пара целых чисел n, k (1 ≤ n ≤ 109, 0 ≤ k ≤ 106).

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

Выведите целое число a — остаток значения искомой суммы, при делении на число 109 + 7.

Примеры
Входные данные
4 1
Выходные данные
10
Входные данные
4 2
Выходные данные
30
Входные данные
4 3
Выходные данные
100
Входные данные
4 0
Выходные данные
4