Задачи
Биномиальный коэффициент
Биномиальный коэффициент
Наш герой работает над исследованием, связанным с треугольником Паскаля, уже около месяца. Недавно он нашел новую задачу для исследования. Ему надо вычислить большое число. Но он очень занят. Можете ли Вы ему помочь?
Имеется бином вида (\textbf{a}*\textbf{x} + \textbf{b}*\textbf{y})^n. Найдите биномиальный коэффициент при \textbf{x^k}^\{ \}* \textbf{y^\{n-k\}} по модулю \textbf{10^9}^\{ \}+ \textbf{7}.
\InputFile
Заданы \textbf{4} целых числа: \textbf{a}, \textbf{b}, \textbf{n} и \textbf{k} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{100}, \textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}, \textbf{1} ≤ \textbf{k} ≤ min(\textbf{n}, \textbf{10^5})).
\OutputFile
Вывести биномиальный коэффициент при \textbf{x^k}^\{ \}* \textbf{y^\{n-k\}} по модулю \textbf{10^9} + \textbf{7}.
Входные данные #1
1 1 4 2
Выходные данные #1
6