ASUMHARD - A Summatory (HARD)

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


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 NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Harder version of A Summatory problem.

hide comments
2023-09-24 22:37:41
Superb problem! Learnt a lot of things :D
2021-10-29 03:07:47 David
Awesome problem! Worked on this problem for over a year.
2021-07-21 17:42:24
hints:
f(n)=1^k+2^k+3^k...n^k
f(n) is a polynomial of degree (k+1)
suppose g(n)=f(1)+f(2)+f(3)...f(n)
g(n) will be a polynomial of degree (k+2)
to calculate f(n) we need to insert k+2 datapoints first
to calculate g(n) we need to insert k+3 datapoints
so now, two lagrange polynomial is needed, first one will be used to calculate f(n) and from the second lagrange, we can calculate g(n)


Last edit: 2021-07-21 17:43:50
2017-08-18 15:34:36 mike
precomputation! precomputation! precomputation!
2017-02-10 13:40:59 Francky
With new compiler my old PY3 code now get AC. Nice.
2014-10-17 14:22:46 Gaurav Kumar Verma
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
2014-09-21 19:33:34 lautner
Plz any Coding_Rockstar, Suggest me hint which algo required by this problem to solve under given time? Any help appreciated. Thnx
2014-06-08 04:21:26 Mitch Schwartz
After solving this, you may be interested to try SOMESUMS :)
2014-06-03 20:42:46 (Tjandra Satria Gunawan)(曾毅昆)
@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)
2014-05-25 12:51:04 [Lakshman]
Finally Accepted!!!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.