ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1675. Лунокод 2

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

Исходные данные

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

Результат

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

Примеры

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