Биномиальный коэффициент

Наш герой работает над исследованием, связанным с треугольником Паскаля, уже около месяца. Недавно он нашел новую задачу для исследования. Ему надо вычислить большое число. Но он очень занят. Можете ли Вы ему помочь?

Имеется бином вида (a*x + b*y)^n. Найдите биномиальный коэффициент при x^k^{ }* y^{n-k} по модулю 10^9^{ }+ 7.

Входные данные

Заданы 4 целых числа: a, b, n и k (1 ≤ a, b ≤ 100, 1 ≤ n ≤ 10^6, 1 ≤ k ≤ min(n, 10^5)).

Выходные данные

Вывести биномиальный коэффициент при x^k^{ }* y^{n-k} по модулю 10^9 + 7.

Примеры