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
krish_patel_07: 2024-03-09 04:22:31

I am solving from 30 minitues and i came to know that 1e7+7 is given as modulo.

mradul_2212: 2023-11-05 12:24:40

make sure you have read the question properly. that it is saying when to terminate the program -> when you encounter 0 0 stop!!

Last edit: 2023-11-06 20:19:10
tejaswini_526: 2023-10-21 11:20:53

can't I use ** in python? Please someone explain me, It says TLE

tr1_ten: 2023-06-23 11:08:09

wtf with mod, i waste so much time with 10^9 + 7 just to realize it is 10^7 + 7 ...

arq_2002: 2023-02-13 12:12:13

Got it saw the hint where he said use pen and paper lol seems like I am rusty as hell

starlove54: 2023-02-06 06:41:07

good question

Last edit: 2023-02-06 07:22:17
mishkat007: 2022-09-15 15:52:47

Is the equation correct after solving??

Zn+Zn-1 -2Zn-2 = n^k + n^n + (n-1)^k + (n-1)^(n-1) - 2(n-2)^k - 2(n-2)^(n-2)

taejin_101: 2022-08-04 16:26:41

Hence proved never get afraid just by looking at a question...

wraith_11: 2021-11-23 20:13:54

very easy, just remember mod = 1e7 + 7, and simply try to reduce the equation by +, - and at the end, use binary exponentiation

samrat2825: 2021-11-15 16:51:02

Use 10^7 + 7 and not 10^9+7


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