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

시간 제한2초메모리 제한1024 MB

요약

H×W 격자에서 높이 h 이하, 너비 w 이하이며 서로 겹치지 않는 두 직사각형의 순서쌍 개수를 10^9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 조합론
정답자: 아직 제출이 없습니다

문제

После того, как Копатыч своей тачкой въехал в очередной механизм Пина, тот рассердился и на собрании Смешариков установил новый порядок пользования землёй. Теперь каждый Смешарик, который хочет использовать какой-то участок страны Смешариков, должен его задекларировать в специальной книжечке, хранящейся у Ёжика. Страну Смешариков можно представить в виде клетчатого прямоугольника с вертикальной стороной $H$ и горизонтальной стороной $W$ .

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

Чтобы предотвратить споры, Ёжик сказал Нюше и Совунье, чтобы они заранее договорились, кому какой участок нужен, и только потом шли записываться в книжечку. Также он установил некоторые правила:

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

Теперь Совунья и Нюша стоят дома у Ёжика перед картой и перебирают все варианты, как они могли бы выбрать два прямоугольника. Помогите Ёжику оценить, на сколько затянется это нарушение личных границ, и найдите число способов выбрать два прямоугольника, удовлетворяющих указанным ограничениям. Это число может быть достаточно велико, так что вычислите его по модулю $10^9 + 7$ .

입력

В первой строке даны два целых числа $H$ и $W$ --- высота и ширина страны Смешариков ( $1 \le H, W \le 10^9$ ). Во второй строке даны два целых числа $h$ и $w$ --- максимальная разрешённая высота и ширина прямоугольников ( $1 \le h, w \le 3 \cdot 10^5$ ; $h \le H$ ; $w \le W$ ).

출력

Выведите одно целое число --- остаток при делении на $10^9+7$ количества способов Совунье и Нюше выбрать место под спортивную площадку и под кордебалетную зону.

힌트

В первом примере страна Смешариков состоит всего из одной клетки, и в неё не вместить два непересекающихся прямоугольника, каждый из которых содержит хотя бы одну клетку.

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

В третьем примере есть ровно $119\\,493\\,408\\,836\\,453\\,856=\left(10^9+7\right)\cdot 119\\,493\\,408$ способов, так что ответ 0.

예제3

예제 1
입력
```
1 1
1 1
```
예상 출력
```
0
```
예제 2
입력
```
2 3
1 2
```
예상 출력
```
70
```
예제 3
입력
```
331 177
102 107
```
예상 출력
```
0
```