Для заданих цілих чисел $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 $$ \InputFile Складається з декількох тестів. Кожен тест міститься в одному рядку, в якому знаходяться два додатних цілих числа $n$ та $k~(1 < n < 2 \cdot 10^8, 0 < k < 10^6)$. Останній тест містить два нулі та не обробляється. \OutputFile Для кожного тесту виведіть відповідь в окремому рядку.