Конфлікт інтересів#11062

Конфлікт інтересів

1 секунда

128 мегабайтів

Середня

Після того, як Копатич своєю тачкою в'їхав у черговий механізм Піна, той розсердився і на зібранні Смішариків встановив новий порядок користування землею. Тепер кожен Смішарик, який хоче використовувати якусь ділянку країни Смішариків, повинен її задекларувати у спеціальній книжечці, що зберігається у Їжачка. Країну Смішариків можна уявити у вигляді клітинчастого прямокутника з вертикальною стороною $H$ і горизонтальною стороною $W$ .

Наступного дня рівно о 8:01 до дверей Їжачка одночасно примчали Совунья і Нюша: Совунья хотіла виділити місце під спортивний майданчик, а Нюші потрібна була зона для вправ з кордебалету.

Щоб запобігти суперечкам, Їжачок сказав Нюші і Совуньї, щоб вони заздалегідь домовилися, кому яка ділянка потрібна, і тільки потім йшли записуватися в книжечку. Також він встановив деякі правила:

Обидві ділянки повинні бути непорожніми підпрямокутниками країни Смішариків.
Висота кожного з прямокутників не може перевищувати $h$ , а ширина - $w$ .
Прямокутники не повинні мати спільних клітинок (але можуть торкатися).

Тепер Совунья і Нюша стоять вдома у Їжачка перед картою і перебирають всі варіанти, як вони могли б вибрати два прямокутники. Допоможіть Їжачку оцінити, наскільки затягнеться це порушення особистих кордонів, і знайдіть число способів вибрати два прямокутники, що задовольняють зазначеним обмеженням. Це число може бути досить великим, тож обчисліть його за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

У першому рядку дано два цілих числа $H$ і $W$ ( $1 \leq H, W \leq 1 0^{9}$ 1 \leq H, W \leq 10^9) - висота і ширина країни Смішариків. У другому рядку дано два цілих числа $h$ і $w$ ( $1 \leq h, w \leq 3 \cdot 1 0^{5}$ 1 \leq h, w \leq 3 \cdot 10^5, $h \leq H$ h \leq H, $w \leq W$ w \leq W) - максимальна дозволена висота і ширина прямокутників.

Вихідні дані

Виведіть одне ціле число - залишок при діленні на $1 0^{9} + 7$ 10^9 + 7 кількості способів Совуньї і Нюші вибрати місце під спортивний майданчик і під кордебалетну зону.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі країна Смішариків складається всього з однієї клітинки, і в неї не вмістити два непересічних прямокутника, кожен з яких містить хоча б одну клітинку.

Нижче на картинці вказано $35$ способів розмістити спортивний майданчик (червоний прямокутник) і кордебалетну зону (зелений прямокутник) у другому прикладі. Решта $35$ способів отримаються, якщо поміняти кольори прямокутників місцями.

У третьому прикладі є рівно $119493408836453856 = (1 0^{9} + 7) \cdot 119493408$ 119 493 408 836 453 856 = (10^9 + 7) \cdot 119 493 408 способів, тож відповідь $0$ .