eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

(Z_n + Z_{n-1} - 2 \cdot Z_{n-2})~mod~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 10^8, 0 < k < 10^6). Последний тест содержит два нуля и не обрабатывается.

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

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

Пример

Входные данные #1
10 3
9 31
83 17
5 2
0 0
Выходные данные #1
4835897
2118762
2285275
3694