Біноміальний коефіцієнт

Наш герой вже близько місяця працює над дослідженням, пов'язаним з трикутником Паскаля. Нещодавно він знайшов нове завдання для вивчення. Йому потрібно обчислити велике число, але він дуже зайнятий. Чи можете ви йому допомогти?

Розглянемо біном виду (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.

Приклади