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

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

Gaurav Narula: 2016-02-29 12:19:43

Python TLE, Java TLE with fast io. Same logic with C AC :/

farhan764: 2016-01-31 16:15:55

modular exponentiation.......use wiki and math world

lakshay_v06: 2016-01-25 12:22:42

After simplifying the equation, you will have to use Modular exponentiation... :) -> MY 88th.

Last edit: 2016-01-25 12:24:26
darkhire21: 2015-12-24 06:44:52

In first go ...!!!

Vipul Srivastava: 2015-12-08 09:54:39

Same code gives TLE in Python


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