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
subodh898: 2019-10-28 13:44:01

just solve the final relation given in terms of n and use binary exponentiation. Also careful about the mod, it is 1e7+7.

destiny_gamer: 2019-10-01 13:54:45

AC in one go! Finaally!

a_l_o_n_e: 2019-08-29 16:27:05

AC in one go!!!

sicklesplit: 2019-08-22 16:02:19

Reemember that 1e7+7 is not prime.

sea_26: 2019-07-29 20:07:02

AC in one go with 0.01 Sec

shreyash1999: 2019-07-01 14:05:26

i m getting all answers correct except 10 3 it is comming negative value in have taken long long also

mubasshir00: 2019-05-22 21:48:34

Just Use Binary Exponentiation and Sum of N number formula :-p then GET AC and thanks me

yashraj_: 2019-01-07 15:57:48

Something to learn for beginners

masterchef2209: 2018-12-22 13:48:31

#ACin1GO

tanardi gunawan: 2018-11-02 10:32:30

aci no nego


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