Bachelor pursuing
Не взнавши імені дівчини у попередній задачі, Саша вирішив навести довідки, благо база дани університету і ВКонтакті завжди під рукою. Виявилось, що Іра — вже чотири рокм як відмінниця — твердо вирішила отримати степінь бакалавра, і, як вияснилось потім, степінь магістра та степінь кандидата наук. І мало що ще далі?..
— Скільки ж це буде в сумі? — у захваті думав Саша, при цьому підсвідомо згадуючи задачу з нещодавнього контесту, яку він так і не розв'язав: задано два числа N та K, обчислити
Вхідні дані
У першому рядку задано число Q (1 ≤ Q ≤ 41000) — кількість запитів. У кожному з Q наступних рядків задано два числа N (1 ≤ N ≤ 10^9) та K (1 ≤ K ≤ 1000).
Вихідні дані
Для кожного запиту у окремому рядку вивести одне число — суму K-их степенів натуральних чисел від 1 до N по модулю 1000000007 .