Просто просуммируйте

Очень простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

Для заданных целых чисел $n$ и $k$ найдите

(Z_{n} + Z_{n - 1} - 2 \cdot Z_{n - 2}) m o d 10000007,

где

Z_{n} = S_{n} + P_{n},

S_{n} = 1^{k} + 2^{k} + 3^{k} + ... + n^{k},

P_{n} = 1^{1} + 2^{2} + 3^{3} + ... + n^{n}

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

Состоит из нескольких тестов. Каждый тест состоит из одной строки, содержащей два положительных целых числа $n$ и $k (1 < n < 2 \cdot 1 0^{8}, 0 < k < 1 0^{6})$ . Последний тест содержит два нуля и не обрабатывается.

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

Для каждого теста выведите ответ в отдельной строке.

Примеры

Ввод #1

Ответ #1

Отправки 1K

Коэффициент принятия 43 %