SUMPOWK1 - Sum of Powers

Given two integers N and K you have to calculate:

Input

The first line of the input is T (1 <= T <= 105), the number of test cases.

Then T lines each line consist of N (1 <= N <= 1018) and K (0 <= K <= 5)

Output

Print the answer modulo 100,000,007 (108 + 7).

Example

Input:
3
5 2
1 5
10 3

Output:
55
1
3025

Added by:Hasan Jaddouh
Date:2013-04-30
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2014-04-16 17:26:05 [Lakshman]
I really don't understand the reason of WA for this easy problem.
--ans(Francky)--> IO are good. Did you notice the modulo 10⁸+7, and not 10⁹+7 ?
-->Ohhhh silly mistake ..Thanks

Last edit: 2014-04-16 18:01:34
2013-05-02 14:57:05 Francky
It's a good tutorial problem, I would like to recommend it to some friends, but I want it to be python3 feasible, please increase time limit to let all common languages a chance to get AC with normal IO. Thanks for taking that into consideration.

RE: increased it to 2s , rejudged your python3 submission and you got AC, I hope you are happy now
--ans(francky)--> Happy no, but satisfied yes. Thanks for that. Now, I recommend this problem to my beginners friends.

Last edit: 2013-05-02 18:09:53
2013-05-01 20:00:48 Francky
There is a search engine here, and you can browse the problems. Not all, but you can sort them by number of solvers, I recommend you to read all with many solvers.

Moreover time limit isn't enough for slow language like python3. You should let at least 1s, no bad solution will pass even with a fast language.

RE: done

--ans(francky)--> It's not enough for python3 (for beginners), please increase a little.

Last edit: 2013-05-02 10:04:10
2013-05-01 17:46:18 [Lakshman]
Please increase the time limit for slow languages like java....

RE: done, I think it's enough, just try to optimize your solution

Last edit: 2013-05-01 18:24:47
2013-05-01 15:51:16 Francky
It is tutorial!
@psetter : please let in classical only problem that are not yet present in database ; this one already exists with harder constraints.

Edit : and you have to set better time limit, to allow slow language to get AC.

RE: yes of course I won't create similar problems, but how can I know if my problems is already exist or not before creating it ?

Last edit: 2013-05-01 18:33:20
2013-05-01 14:45:06 devu
Poor Problem .. Move it to Tutorial

RE: at least you couldn't get AC from first time :P

RE: :D OverFlow Problems :D

Last edit: 2013-05-03 01:50:05
2013-05-01 13:53:38 yaswanth
can u please tell me where is the mistake in my code??


RE: your program fails when N is very huge (i.e N>10^12)
ya I got it just a few seconds back!! anyways thank you!!

Last edit: 2013-05-06 12:03:58
2013-05-01 11:43:37 (Tjandra Satria Gunawan)(曾毅昆)
this is much easier than my ASUMHARD problem :-P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.