Лунокод 2#5885

Лунокод 2

1 секунда

64 мегабайти

Складна

Можна згадати, що спосіб кодування інформації, нині відомий як лунокод, був винайдений місячними програмістами під час оборонної війни проти марсіан. Навіть зараз його дещо модифікована версія використовується місячниками для передачі даних. Дані представляються у вигляді матриці розміром $M \times N$ M \times N, що містить лише одиниці та нулі. Передана матриця повинна задовольняти наступній умові: рівно $K$ її рядків і рівно $L$ її стовпців мають складатися лише з нулів. Якщо отримана матриця не задовольняє цій умові, то вважається, що дані були спотворені під час передачі.

Вхідні дані

У єдиному рядку через пропуск записано $4$ цілих числа: $M, N, K, L$ M, N, K, L ( $1 \leq M, N \leq 100000$ 1 \leq M, N \leq 100\,000, $0 \leq K \leq M$ 0 \leq K \leq M, $0 \leq L \leq N$ 0 \leq L \leq N).

Вихідні дані

Виведіть кількість таких матриць по модулю $1 0^{9} + 7$ 10^9+7.

Приклади

Приклад 1