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?.. --- \textit{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 \textbf{N} and \textbf{K}, compute \includegraphics{https://static.e-olymp.com/content/bb/bb6cfd02c724d122569ca196cc4dba49c5942363.jpg} \InputFile The first line contains \textbf{Q} (\textbf{1} ≤ \textbf{Q} ≤ \textbf{41000}) --- the number of queries. Each of the following \textbf{Q} lines contains two numbers \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^9}) and \textbf{K }(\textbf{1} ≤ \textbf{K} ≤ \textbf{1000}). \OutputFile For each query on a separate line write one number --- the sum of \textbf{K}-th powers of positive integers from \textbf{1} to \textbf{N} modulo \textbf{1000000007} .