Problems
Sum of Powers Version I
Sum of Powers Version I
\includegraphics{https://static.e-olymp.com/content/4a/4abc1ac02d209399414a8275d73c262e643c48d1.jpg}
Given \textbf{N} and \textbf{K}, compute () \textbf{mod 1000000007}.
\InputFile
The first line of the input gives an integer \textbf{T}, which is the number of test cases. Each test case consists of a line containing \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000000000}) and \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{4}).
\OutputFile
\includegraphics{https://static.e-olymp.com/content/4a/4abc1ac02d209399414a8275d73c262e643c48d1.jpg}
For each test case output () \textbf{mod 1000000007}.
Input example #1
5 5 1 4 2 1000000000 1 1000000000 2 1000000000 3
Output example #1
15 30 21 999999916 441