## 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```

 < Previous 1 2 3 4 5 6 7 8 9 Next > 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 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