Mike is sick of listening to concerts during lunchtime at his school! Unfortunately for him, a single concert will be hosted on the school field on each of the next days.
The school field can be represented as a rectangle with the bottom-left corner and upper-right corner on a 2-D Cartesian plane, and the location of each concert can be represented by a single point within the rectangle. There is also a concession area, whose initial location can be represented as a rectangle with the bottom-left corner and upper-right corner .
On the first day, the concert will be hosted at . At the end of the -th day, the concert will be moved by units to the right and units upwards. To maximize attraction, the concession stand will adjust accordingly and move its upper-right corner units upwards. Note that the bottom-left corner of the concession area always remains at .
Since Mike does not like listening to repetitive music and would much rather buy snacks from the concession, he wants to choose a rectangular region within the school field to eat his lunch such that over the days, no point within the rectangular region is ever closer to the concert than the concession area, in terms of Euclidean distance. The rectangular region must be axis-aligned, have a positive area, and the bottom-left corner and upper-right corner of the rectangle must have integral coordinates.
The distance between a point and the concession area is defined as the shortest Euclidean distance between the point and any point inside the rectangular region, including on its boundary. Of course, if a point resides within the concession area, its distance to the concession area is .
Can you help Mike find the number of possible rectangle regions that he can eat his lunch at over the next days? Since this value may be large, output it modulo .
It is guaranteed that each concert will remain within the school field, possibly on its boundary.
It is guaranteed that the -coordinate of the concession area will always be positive.
Subtask 1 [15%]
Subtask 2 [15%]
Subtask 3 [35%]
Subtask 4 [35%]
No additional constraints.
The first line contains three integers, , and .
The second line contains two integers, and .
The next lines contain two integers, and , representing the horizontal shift and vertical shift of the concert at the end of the -th day.
On a single line, print the number of possible rectangular regions that Mike can choose modulo .
Sample Input 1
2 5 4 2 2 1 1
Sample Output 1
Explanation for Sample Output 1
One possible rectangular region that Mike can select is highlighted yellow in the diagram below. It can be shown that no point within this rectangle is closer to the concert than the concession area on either day.
Sample Input 2
1 2 2 1 2
Sample Output 2
Explanation for Sample Output 2
The possible rectangular regions that Mike can select are shown below.
Sample Input 3
3 1000000 1000000000 101010 101010101 101010 101010101 101010 101010101
Sample Output 3
Explanation for Sample Output 3
Be sure to print the result modulo .
Sample Input 4
6 49 20 9 10 21 0 -30 10 49 -5 0 0 -9 -4
Sample Output 4