ZSUM - Just Add It

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.

Constraints

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:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Manohar Singh

hide comments
2015-10-01 07:15:36 MishThi
Python :( TLE

Last edit: 2015-10-01 07:15:49
2015-09-15 07:29:01 Ravi Chandra
Hey my 54th
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
2015-08-26 20:39:36
simple question the task is to use effective algo for power of 2 numbers.. :)
2015-08-22 07:54:00 Shivam Singh
Interesting question to hit the 75th milestone :)
2015-08-15 19:06:55 ROHIT Kumar
watch carefully some terms are cancelling out accepted in one go.....:)

Last edit: 2015-08-15 19:22:29
2015-08-13 19:15:00 Mohd Ausaf Jafri
use right to left binary exponentiation
2015-08-08 15:41:58 Nilutpal Borgohain
simple expansion! kudos!
2015-06-29 11:16:47 Arpit Gupta
Modular exponentiation'll help a lot...:)

Last edit: 2015-06-29 11:17:04
2015-06-20 18:32:23 Sejal Vaghela
Thanks @ deadbrain
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.