Advertisement blocking software were detected ;( Please add this webpage to whitelist.

ZSUM - Just Add It

no tags 

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:0.180s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All
Resource:Manohar Singh

hide comments
pvsmpraveen: 2015-08-29 07:46:30

Got AC, You will definitely learn something from this problem, I spent around 1.5 hour and its worth for it ;)

Last edit: 2015-08-29 07:47:01
prakash_reddy: 2015-08-26 20:39:36

simple question the task is to use effective algo for power of 2 numbers.. :)

Shivam Singh: 2015-08-22 07:54:00

Interesting question to hit the 75th milestone :)

ROHIT Kumar: 2015-08-15 19:06:55

watch carefully some terms are cancelling out accepted in one go.....:)

Last edit: 2015-08-15 19:22:29
Mohd Ausaf Jafri: 2015-08-13 19:15:00

use right to left binary exponentiation

Nilutpal Borgohain: 2015-08-08 15:41:58

simple expansion! kudos!

Arpit Gupta: 2015-06-29 11:16:47

Modular exponentiation'll help a lot...:)

Last edit: 2015-06-29 11:17:04
Sejal Vaghela: 2015-06-20 18:32:23

Thanks @ deadbrain

divine_himani: 2015-06-11 18:11:07

Python coders please do not attempt the problem, it will be a total waste of time as will always get a TLE

Aman Agarwal: 2015-06-06 09:16:04

Modular exponentiation would help
100th classical on spoj ;)