Count sets of two points on each of two parallel lines that form a trapezoid with both bottom angles acute or both top angles acute.
Medium7GeometrySortingCombinatoricsTwo pointersNo attempts yetTime limit1sMemory limit128 MBonionpringles set his last problem on September 10 and enlisted on September 11. The unit he joined had plenty of odd senior soldiers. One of them found out that he had studied mathematical sciences at KAIST and told him this.
"We have to pitch a tent right now. See those two parallel ropes over there, with stakes driven in here and there along them? We pick four of those stakes and pitch the tent on exactly those. Our unit has a tradition: the base of the tent must be a trapezoid whose two bottom angles are both acute, or whose two top angles are both acute. Keep building any tent that follows the tradition. Once one pleases me, I will let you stop."
onionpringles went pale and started counting how many different tents he would have to build in the worst case. Count the number of different tents for him. Two tents are the same when the set of stakes forming the base is the same.
The two ropes are the horizontal lines y=y1 and y=y2, and every stake is a point on one of them.

The picture above shows a small example. The two drawings on top do not satisfy the condition, and the two at the bottom do.
The first line contains the number of stakes on each of the two ropes, N and M, and the y coordinates of the two ropes, y1 and y2, separated by spaces. (2≤N,M≤100000, −1000000000≤y1,y2≤1000000000, y1=y2)
Each of the next N lines contains the x coordinate of a stake on the rope y=y1, one per line. Each of the following M lines contains the x coordinate of a stake on the rope y=y2, one per line. Every x coordinate is an integer between −1000000000 and 1000000000. No two stakes on the same rope share an x coordinate.
Print the number of trapezoids that satisfy the condition, modulo 1000000007.