SP11695 ASUMHARD - A Summatory (HARD)

f(n) is defined as: f(n) = 1 $ ^{k} $ +2 $ ^{k} $ +3 $ ^{k} $ +...+n $ ^{k} $ , so it is the sum of the k-th power of all natural numbers up to n. In this problem you are about to compute, f(1) + f(2) + f(3) + ... + f(n)

The first line is an integer **T**(1 T T test cases follow. For each test case, there are two integers **n**(1 n k(0 k

For each test case output the result of the summatory function described above. Since this number could be very large, output the answer modulo 1,234,567,891.