Məsələlər
Binomial Coefficient
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.
Giriş verilənləri
You are given 4 integers: a, b, n and k (1 ≤ a, b ≤ 100, 1 ≤ n ≤ 10^6, 1 ≤ k ≤ min(n, 10^5)).
Çıxış verilənləri
Output the binomial coefficient of x^k^{ }* y^{n-k} modulo 10^9 + 7.
Nümunə
Giriş verilənləri #1
1 1 4 2
Çıxış verilənləri #1
6