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
sadiq252: 2021-09-12 19:05:48

Nice problem!Solved by first try,used binary exponentiation.

curiousyuvi: 2021-05-28 06:33:53

ac in one go...hint: solve the equation Zn+Zn-1 -2Zn-2....: )

anchord: 2021-05-27 06:13:49

Tbh, this problem was worth of thinking, thanks for this problem, i learned so much from this:3

srivathsav1410: 2021-05-09 13:43:22

easy one ac in one go just n=5 and k=2 you will get it

abuhanif: 2021-04-19 17:28:14

@sakshi_38 n is always greater than 1 see constrain 1<n<200000000

sakshi_38: 2021-02-05 07:58:40

what will be the answer when n=1?

makdi: 2020-12-01 08:05:39

Be careful , wasted half an hour because it is 10^7 + 7 and not 10^9+7

aa18: 2020-10-13 18:59:24

Why recursive approach of modular exponentiation is giving WA but iterative got accepted.

kishlay1105: 2020-07-26 21:29:22

Just take a pen and paper and solve the above expression , many terms will get cut and you will get a small expression which will be solved using modular exponentiation :)

coolboy7: 2020-07-26 19:41:33

@ashish try to solve the expression first you will see that some terms will be cancelling


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