2020 Цикл Интернет-олимпиад для школьников, первая командная олимпиада, 18 октября
Conflict of interests
After Kopatych drove his wheelbarrow into another mechanism of Pin, he got angry and at the Smeshariki meeting established a new procedure for using the land. Now every Smesharik who wants to use some part of the country of Smeshariki must declare it in a special booklet kept by the Hedgehog. The Smeshariki country can be represented as a checkered rectangle with a vertical side H and a horizontal side W.
The next day, at exactly 8:01, Sovunya and Nyusha rushed to the door of the Hedgehog at the same time: Sovunya wanted to allocate space for a sports ground, and Nyusha needed an area for corps de ballet exercises.
To prevent disputes, the Hedgehog told Nyusha and Sovunya to agree in advance who needs which area, and only then go to sign in the book. He also set some rules:
Both areas must be non-empty sub-rectangles in Smeshariki country.
The height of each of the rectangles cannot exceed h, and the width cannot exceed w.
Rectangles must not have common cells (but can touch).
Now Sovunya and Nyusha are standing at Hedgehog's house in front of the map and sorting through all the options, how could they choose two rectangles. Help the Hedgehog estimate how long this violation of personal boundaries will take, and find the number of ways to choose two rectangles that satisfy the indicated restrictions. This number can be quite large, so calculate it modulo
10^9 + 7.
The first line contains two integers H and W (1 ≤ H, W ≤
10^9) - the height and the width of Smeshariki country. The second line contains two integers h and w (1 ≤ h, w ≤ 3 *
10^5, h ≤ H, w ≤ W) - maximum allowed height and width of rectangles.
Print one integer - the remainder after dividing by
10^9 + 7 the number of ways Sovunya and Nyusha can choose a place for a sports ground and a corps de ballet area.
1 1 1 1
2 3 1 2
331 177 102 107
In the first example, the Smeshariki country consists of only one cell, and it cannot contain two non-intersecting rectangles, each of which contains at least one cell.
The picture below shows 35 ways to place the sports ground (red rectangle) and the chorus de ballet area (green rectangle) in the second example. The remaining 35 ways will be obtained by swapping the colors of the rectangles.
In the third example, there are exactly 119 493 408 836 453 856 = (
10^9 + 7) * 119 493 408 ways, so the answer is 0.