Binomial Coefficient

Our hero 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: a, b, n and k (1 ≤ a, b ≤ 100, 1 ≤ n ≤ 10^6, 1 ≤ k ≤ min(n, 10^5)).

Output

Output the binomial coefficient of x^k^{ }* y^{n-k} modulo 10^9 + 7.

Examples