eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Лунокод 2

Лунокод 2

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Немногие помнят, что способ кодирования информации, известный ныне как лунокод, был изобретён ещё в ходе лунно-марсианской войны. С незначительными модификациями он и сейчас используется лунатиками для передачи данных. Передаваемая информация в виде набора нулей и единиц записывается в матрицу размером M×N. На матрицу наложено следующее ограничение (контрольное условие): у неё должно быть ровно K нулевых строк и ровно L нулевых столбцов. Если после приёма оказывается, что полученная матрица не удовлетворяют контрольному условию, значит, некоторое количество её ячеек было искажено при передаче.

В ходе отчёта перед президентом Лунной Федерации министр связи предложил провести реформу лунокода. Министр аргументировал это тем, что количество различных сообщений, которые могут быть переданы, не так уж и велико. Президент поручил министерству совместно с Лунной Академией Наук исследовать данный вопрос, чтобы решить, действительно ли необходима реформа. В ходе исследования оказалось, что министр заблуждался: ведь при достаточно больших M и N количество матриц из нулей и единиц размера M×N, удовлетворяющих контрольному условию, огромно. Сможете ли вы определить, сколько их?

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

В единственной строке через пробел записаны 4 целых числа: M, N, K, L (1M, N100000, 0KM, 0LN).

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

Как было уже сказано, количество искомых матриц может быть очень велико, поэтому нет нужды выдавать его полностью. Выведите остаток от деления этого числа на 10^9+7.

Пример

Входные данные #1
2 2 0 0
Выходные данные #1
7
Автор Игорь Чевдарь
Источник Ural SU Contest. Petrozavodsk Summer Session, August 2008