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.

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

hide comments
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 ;)

THECOLDONE: 2015-05-27 20:57:00

thanks @ deadbrain

deadbrain: 2015-01-27 14:55:09

for those who don't know how to solve the problem efficiently, read Modular exponentiation wiki article first... Lot to learn from this question.

sarelfeniel: 2014-05-03 09:28:40

Great problem.

@Francky I hope one day to discover the secrets that you seem to have found!


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