Sphere Online Judge

SPOJ Problem Set (classical)

9494. Just Add It

Problem code: ZSUM


For two given integers n and k find (Zn+Zn-1-2Zn-2)mod 10000007 , where Zn=Sn+Pn and Sn=1k+2k+3k+…..+nk and Pn=11+22+33+……+nn.

Input

There are several test cases [ ≤10000 ].In each case two space separated positive integers n and k are given.
For last test case n and k are given  as 0  0 ,which is  not to be processed.
1<n<200000000 , 0<k<1000000.

Output

For each case print the asked value in separate line.

Example

Input:
10 3
9 31
83 17
5 2
0 0 
Output:
4835897
2118762
2285275
3694

Added by:Manohar Singh
Date:2011-09-04
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:Manohar Singh

hide comments
2014-05-27 16:26:21 `Ak
finally got AC... after one TLE :)
2014-05-03 09:28:40 sarelfeniel
Great problem.

@Francky I hope one day to discover the secrets that you seem to have found!
2014-03-19 04:37:22 free mind ;)
one extra function call give me 4 tle :D
2014-03-05 13:41:03 Anubhav Balodhi
Easy one, but needs a lot of hard work on removing TLE in few languages like python. had to go back to C++ ;-)
2014-01-22 18:59:35 Abhinav Gupta
Easy ques!!..Just Mathematics..
2014-01-21 23:11:21 paras meena
Easy Math :)
2013-12-29 19:34:05 Pranye Mawai
easy.. jus think mathematically.. ;)
2013-12-15 09:41:55 SanchitK
used MOD expo.. but still gives TLE. :(
2013-11-27 07:29:44 Saimadhav Heblikar
50th on spoj!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.