Our hero - Maga has been working on a research related to Pascal’s Triangle for about a month. He has recently found a new problematic thing for his research. He has to calculate a big number. But he is very busy. Could you do it for him?

You are given a binomial as this: (a * x + b * y)^n. You have to find the binomial coefficient of x^k * y^(n-k) modulo 10^9+7.

Input:

You are given 4 integers: each space separated integers a, b, n and k.

Output:

Output 1 integer: the binomial coefficient of x^k * y^(n-k) mod (10^9+7).

Constraints:

1 ≤ a, b ≤ 100

1 ≤ n ≤ 10^6

1 ≤ k ≤ min(n,10^5)

SAMPLE INPUT
1 1 4 2

SAMPLE OUTPUT
6

Explanation

The result is 6. In the (x+y)^4 binomial, the coefficient of x^2 * y^2 is 6.

见题面

见题面