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 kth power of all natural numbers up to n.
In this problem you are about to compute,
f(1) + f(2) + f(3) + ... + f(n)
Input
The first line is an integer T(1 ≤ T ≤ 54,321), denoting the number of test cases. Then, T test cases follow.
For each test case, there are two integers n(1 ≤ n ≤ 123,456,789) and k(0 ≤ k ≤ 321) written in one line, separated by space.
Output
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.
Example
Input: 5
2 3
10 3
3 3
100 0
100 1 Output: 10
7942
46
5050
171700
Warning: A naive algorithm may not run in time
hide comments
mike:
20170818 15:34:36
precomputation! precomputation! precomputation! 

Francky:
20170210 13:40:59
With new compiler my old PY3 code now get AC. Nice. 

Gaurav Kumar Verma:
20141017 14:22:46
getting TLE :(


lautner:
20140921 19:33:34
Plz any Coding_Rockstar, Suggest me hint which algo required by this problem to solve under given time? Any help appreciated. Thnx 

Mitch Schwartz:
20140608 04:21:26
After solving this, you may be interested to try SOMESUMS :) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140603 20:42:46
@Blasters: Not only TLE, your code is also giving wrong output. Your complexity is fast enough, maybe there are some bug on your implementation (i don't have time to find it) 

[Lakshman]:
20140525 12:51:04
Finally Accepted!!!!!! 

Blasters:
20140520 15:04:45
@Tjandra Can you please tell why i am getting tle ID NO 11612132 I used O(t*k) + k^2 algo with fast i/o and on ideone the worst case runs in 4.5 sec Last edit: 20140520 15:05:12 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140209 22:57:40
@Francky: Congratulations :)


Francky:
20140208 14:39:17
Fast IO bring me from 0.63 to 0.47, and first place. ;). I liked work on this problem, I should have done the job before.

Added by:  Tjandra Satria Gunawan 
Date:  20120607 
Time limit:  2.107s 
Source limit:  12345B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Harder version of A Summatory problem. 