eolymp
bolt
Try our new interface for solving problems
Problems

Binomial Coefficient

Binomial Coefficient

Time limit 0.5 seconds
Memory limit 64 MiB

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 data

You are given 4 integers: a, b, n and k (1a, b100, 1n10^6, 1k ≤ min(n, 10^5)).

Output data

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

Examples

Input example #1
1 1 4 2
Output example #1
6
Author Mahammad Valiyev
Source Local Contest #2 Qafqaz University by Mahammad Valiyev