ASUMHARD - A Summatory (HARD)

no tags 

f(n) is defined as: f(n) = 1k+2k+3k+...+nk, 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)

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

 

See also: Another problem added by Tjandra Satria Gunawan


hide comments
mike: 2017-08-18 15:34:36

precomputation! precomputation! precomputation!

Francky: 2017-02-10 13:40:59

With new compiler my old PY3 code now get AC. Nice.

Gaurav Kumar Verma: 2014-10-17 14:22:46

getting TLE :(
SPOJ submission 12653037 (C++ 4.3.2).

my code is running in 4.5sec on ideone for
1
12345678 321

but for worst case TLE
any hint plz!!!

Last edit: 2014-10-17 18:25:57
lautner: 2014-09-21 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: 2014-06-08 04:21:26

After solving this, you may be interested to try SOMESUMS :)

(Tjandra Satria Gunawan)(曾毅昆): 2014-06-03 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]: 2014-05-25 12:51:04

Finally Accepted!!!!!!

Blasters: 2014-05-20 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: 2014-05-20 15:05:12
(Tjandra Satria Gunawan)(曾毅昆): 2014-02-09 22:57:40

@Francky: Congratulations :)
Btw, Next valentine day (14th Febtuary 2014) I'll set new recurrence problem, It'll be my second hardest problem, I hope you'll like it.. ;)
And welcome back to SPOJ, Francky, glad to 'see' you again..

Francky: 2014-02-08 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.
About complexity : first part O(k^2) -> 0.00s, second part O(T×K) with a good constant : k/2 (modmul+add) per case.
Now, it's 0.39s in C, but I need 1s or 2s to get AC in Py3.

Last edit: 2014-02-08 18:02:33

Added by:Tjandra Satria Gunawan
Date:2012-06-07
Time limit:2.107s
Source limit:12345B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Harder version of A Summatory problem.