403859: GYM101343 A On The Way to Lucky Plaza

Alaa is on her last day in Singapore, she wants to buy some presents to her family and friends. Alaa knows that the best present in the world will be a chocolate plate for each one of her family members and friends.

Alaa goes to Lucky Plaza shopping mall in Orchard road in order to find all chocolate she needs. Lucky Plaza is a big mall and have many shops that sell chocolate.

On the entrance of Lucky Plaza Alaa wondered if she wants to buy k chocolate plates, what is the probability that she will buy the k^th chocolate plate from the n^th shop she will visit, knowing that she can visit each shop at most one time. Also she can buy at most one chocolate plate from each shop, and the probability to do that is p. (This probability is the same for all shops in Lucky Plaza)

Alaa wants to finish her mission as soon as possible, so she starts visiting the shops, also she asked you to calculate the answer of her hard question. Can you?

The first line contains three integers m, n, k and real number p (1  ≤  m, n, k  ≤  10⁵) (0  ≤  p  ≤  1), where m is the number of shops that sell chocolate in Lucky Plaza, n is the number of shops Alaa will visit, k is the number of chocolate plates Alaa wants to buy, and p is the probability that Alaa will buy a chocolate plate from any shop that sell chocolate.

The probability p is given with exactly three digits after the decimal point

On a single line print y, where y is the sought probability computed modulo 10⁹ + 7.

The answer y is defined precisely as follows. Represent the probability that Alaa will buy the k^th chocolate plate from the n^th shop she will visit as an irreducible fraction p / q. The number y then must satisfy the modular equation y × q ≡ p (mod 10⁹ + 7), and be between 0 and 10⁹ + 6, inclusive. It can be shown that under the constraints of this problem such a number y always exists and is uniquely determined.

5 1 1 0.500

500000004

9 4 2 0.800

417600003

100 5 5 0.200

714240005

In the first test case there are 5 shops that sell chocolate in Lucky Plaza, and Alaa wants to buy only 1 chocolate plate. In this case Alaa wants to know what is the probability that she will buy the 1^st chocolate plate from the 1^st shop she will visit. The probability is 1 / 2, and the answer is 500000004, since (500000004 * 2) % (10⁹ + 7) = 1 % (10⁹ + 7).

In the second test case there are 9 shops that sell chocolate in Lucky Plaza, and Alaa wants to buy only 2 chocolate plates. In this case Alaa wants to know what is the probability that she will buy the 2^nd chocolate plate from the 4^th shop she will visit. The probability is 48 / 625, and the answer is 417600003, since (417600003 * 625) % (10⁹ + 7) = 48 % (10⁹ + 7).