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
azelf: 2016-11-05 19:34:35

TLE with java with correct logic

surajmall: 2016-10-04 16:17:48

its some what tricky but but biginners must try it

Abhishek: 2016-09-24 19:04:10

please increase time limit for python, or remove it from the available languages

marshmellow: 2016-08-31 14:40:54

dont get nervous by looking at the description of question... Its very easy when you simplify the equation.
GO FOR IT. YOU WILL LEARN SOMETHING NEW.

sy_117: 2016-08-16 14:47:58

Easy one if u do a little bit of pen paper work !!! mod=10^7+7..........

avidcoder: 2016-07-16 07:53:08

Last edit: 2016-07-16 07:54:26
vineetpratik: 2016-07-05 16:29:50

Simplification.modular exponentiation AC in 0.02 , 1st go :)

ragwave: 2016-05-11 17:28:20

visit this link for refrence
https://en.wikipedia.org/wiki/Modular_exponentiation

Neeraj Joshi: 2016-03-22 17:50:41

50th...

pt97: 2016-03-08 15:29:49

use fu*king mod every where


Added by:Manohar Singh
Date:2011-09-04
Time limit:0.180s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Manohar Singh