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