## 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
 < Previous 1 2 3 4 5 Next > a_mishra4: 2017-10-25 07:28:25 solve given expression and then apply modular exponentiation on remaining terms vishesh197: 2017-09-01 17:19:08 use modular exponentiation and now see the series carefully all n-2 terms of Zn,Zn-1,Zn-2 will get cut off while solving expression Zn+Zn-1-2*Zn-2 .good problem AC in 3rd go... kamlesh_2209: 2017-09-01 07:45:50 AC in one go use modular exponentiation....its a easy problem.... him_novice: 2017-08-31 08:57:05 JAVA--> TLE C---> Accepted in a go. Use modular exponentiaion only subhamiiit: 2017-08-24 22:14:52 my 50th on spoj.....use modular exponentation 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.

 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