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
sagnik_66: 2017-05-20 09:45:01

scanf, printf saved me :3

sagnik_66: 2017-05-20 09:45:00

scanf, printf saved me :3

amalik123: 2017-03-22 11:08:55

modular exponentiation is the key,easy one

nilabja16180: 2017-03-21 17:24:52

Modular Exponentiation don't overthink!

rohit9934: 2017-03-09 18:45:21

Dont think too much,its easy.Just write one function for calculating mod.and then just write that Algebraic Expression in form of one function as a variable.Thats it.AC in 1 go after a long time.(After 1st prob :D) 0.01 sec in C.

nishanth2066: 2017-01-23 15:00:18

TLE in .py AC in C

kass_97: 2017-01-14 10:34:57

No way to get past TLE unless you use modular exponentiation

apurvgs: 2016-12-24 13:18:32

modular exponentiation
AC in on go.............my 50th :-)

rohit_2407: 2016-12-15 12:15:28

learned a new concept !!

venky1001: 2016-12-10 10:28:42

TLE in JAVA :/


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