单点时限: 1.0 sec
内存限制: 256 MB
QQ小方最近沉迷于一款在线多人游戏。在这个游戏里,你可以画出一个简单多边形,这个游戏就会通过三维构图,画出以这个简单多边形作为横截面的无限高的棱柱。
但是最近,这个游戏出现了一个 bug ,有一些玩家构造出的棱柱会无缘无故横过来。程序员正在紧急修复这个 bug ,但是很多玩家却觉得这个 bug 能带给游戏更多的乐趣,并开发了一些新玩法。
现在,QQ小方正在和炮哥玩一个游戏:QQ小方和炮哥两个人构造出两个延伸方向互相垂直的棱柱,QQ小方想要和炮哥比,谁更先算出这两个棱柱的体积交。
QQ小方只会处理横截面是凸多边形的情况,但这次不一样。现在给出这两个简单多边形的横截面,你能帮QQ小方计算出一般情况下的体积交吗?
第一行一个整数 $n$ ( $1 \le n \le 10^5$ ),代表QQ小方给出的多边形顶点数量。
接下来 $n$ 行,第 $i$ 行两个整数 $x_i,y_i$ ( $-10^6 \le x_i,y_i \le 10^6$ ),代表QQ小方画出的多边形上第 $i$ 个点的坐标。
接下来一行一个整数 $m$ ( $1 \le m \le 10^5$ ),代表炮哥给出的多边形的顶点数量。
接下来 $m$ 行,第 $i$ 行两个整数 $p_i,q_i$ ( $-10^6 \le p_i,q_i \le 10^6$ ),代表炮哥画出的多边形上第 $i$ 个点的坐标。
多边形的顶点会以顺时针或逆时针的方向给出。
一行一个整数,代表这两个棱柱体的体积交。
如果这个多边形的体积交的精确值是 $\frac{P}{Q}$ ,输出 $P \times Q^{-1} \mod 10^9+7$ 。
4 10 0 0 10 -10 0 0 -10 3 5 0 -15 -10 -15 10
666667713
样例中两柱体的体积交是 $\frac{3125}{3}$。