Bachelor pursuing
Still not knowing the name of the girl from the previous problem, Sasha decided to make inquiries, he was lucky that he had a database of university and VK at hand. It was found that Ira is an excellent student for four years and wanted to get a bachelor's degree, and as it turned out, a master's degree and PhD. And you never know what else?..
— How much will it be in the sum? — Sasha thought with delight (note: in Russian for "power" and "degree" is used the same word), while subconsciously recalling a recent problem from the contest which he has not solved. Two numbers are given N and K, compute
Input
The first line contains Q (1 ≤ Q ≤ 41000) — the number of queries. Each of the following Q lines contains two numbers N (1 ≤ N ≤ 10^9) and K (1 ≤ K ≤ 1000).
Output
For each query on a separate line write one number — the sum of K-th powers of positive integers from 1 to N modulo 1000000007 .