Binomial Coefficient#7245
Our hero has been conducting research related to Pascal’s Triangle for about a month. Recently, he encountered a new challenge in his studies. He needs to compute a large number, but he is very busy. Can you help him?
You are given the following binomial:
Find the coefficient of the term x^k y^{n-k} in its expansion, modulo 10^9 + 7.
The input consists of four integers: , , , and (1 \le a, b \le 100, 1 \le n \le 10^6, 1 \le k \le \min(n, 10^5)).
Output the coefficient of x^k y^{n-k} in the expansion of (a x + b y)^n, modulo 10^9 + 7.
Example 1