SPOJ.com - Problem ASUMHARD

ASUMHARD - A Summatory (HARD)

no tags

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)

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

Warning: A naive algorithm may not run in time

Submit solution!

hide comments

< Previous 1 2 3 Next >

	sankalp_7: 2023-09-24 22:37:41 Superb problem! Learnt a lot of things :D
	David: 2021-10-29 03:07:47 Awesome problem! Worked on this problem for over a year.
	likhon5: 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
	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!!!!!!

Submit solution!

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.