## Magical-Deforestation

Time Limit: 1 sec
Memory Limit: 256 MB
Attempts: 17
Accuracy: 5.88%
Author: Swapnil Negi

There lives a boy Ketan in the village Kusht. He owns some magical clay and a witty brain. He wants to completely destroy his village by removing the only source of income, trees. There are a total of M varieties of trees with K trees for each variety, so the village has a total of M*K trees. The magical clay is capable of destroying any kind of tree except the holy Sal Tree. So, basically the magical clay can destroy (M-1) kinds of trees.

All the trees are planted in a line in a random order. Ketan plans to place the magical clay in the soil of the first tree. Since the clay is magical it can itself move to the next tree in the line after destroying a particular tree but if the clay reaches the holy Sal tree, it gets destroyed.

All you need to find is the expected number of trees that will be killed in the process. This expected value can be written as a fraction P/Q, where P and Q are coprime. Therefore, you should compute P⋅Q^{−1} modulo 1000000007 (10^{9} + 7) , where Q^{−1} denotes the modular inverse of Q modulo 1000000007.

Input Format:

The only line of input contains 2 numbers M and K.

Output Format:

Print a single line containing one integer — the number equivalent to the expected number of trees killed modulo 1000000007.

Constraints:

1 ≤ M ≤ 10^{12}

1 ≤ K ≤ 10^{6}

Sample Input:

2 1

Sample Output:

500000004

Explanation:

There are only 2 types of trees. Let us number them 1 and 2 (1 is the Holy Sal Tree). The only possible arrangements are [1, 2], [2, 1]. In the first arrangement, no tree gets killed. In the second arrangement, tree type 2 gets killed first and then holy tree will kill the magical clay. So the expected number of killed trees = (½ * 0 + ½ * 1) modulo 10^{9} + 7 = ½ modulo 10^{9} + 7 = 500000004

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

1 year ago

cpp14

0.07 sec

64 KB