Просто підсумуйте

Дуже проста

Обмеження на час виконання 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%