Bachelor pursuing#2846
Sasha, not having learned the girl's name in the previous problem, decided to make inquiries, luckily having access to a database of the local educational institution and a popular social network. It turned out that Ira had been an excellent student for four years and was determined to obtain a bachelor's degree. Later, she also planned to pursue a master's degree and a PhD. And who knows what next?..
— How much will this be in total? — Sasha wondered enthusiastically, subconsciously recalling a problem from a recent contest which he had not solved: given two numbers and , compute
The first line contains (1 \le Q \le 41000) — the number of queries. Each of the next lines contains two numbers (1 \le N \le 10^9) and (1 \le K \le 1000).
For each query, output on a separate line a single number — the sum of the -th powers of natural numbers from to modulo .
Example 1