Здобуття ступеня бакалавра#2846
Саша, так і не дізнавшись імені дівчини у попередній задачі, вирішив навести довідки, благо мав доступ до бази даних місцевого навчального закладу і популярної соціальної мережі. Виявилось, що Іра вже чотири роки була відмінницею і твердо мала намір отримати ступінь бакалавра. Потім вона також планувала здобути ступінь магістра і кандидата наук. А що буде далі — хто знає?..
— Скільки це буде разом? — із захопленням замислився Саша, підсвідомо згадуючи задачу з нещодавнього змагання, яку так і не зміг розв'язати: задано два числа та , обчислити
Перший рядок містить (1 \le Q \le 41000) — кількість запитів. Кожен із наступних рядків містить два числа (1 \le N \le 10^9) та (1 \le K \le 1000).
Для кожного запиту виведіть в окремому рядку одне число — суму -тих степенів натуральних чисел від до за модулем .
Приклад 1