#P18459. Three Rectangles

Three Rectangles

Three Rectangles

题目描述

平面上有一块边与坐标轴平行的矩形板,其左下角为 (0,0)(0,0),右上角为 (H,W)(H,W)。

给定三张矩形卡片,需要将它们完整地放在矩形板内,使三张卡片共同覆盖整块矩形板,并求不同放置方案的数量。卡片不能旋转或翻转,每张卡片的边必须与坐标轴平行,所有顶点坐标都必须是整数。卡片之间允许重叠。

当且仅当存在一张卡片在两个方案中的位置不同,两个方案才被视为不同。因此三张卡片有各自的编号,即使尺寸相同,也不能将它们当作无法区分的卡片。

由于答案可能很大,请输出答案对 109+710^9+7 取模的结果。

输入格式

第一行包含一个整数 TT(1≤T≤1051\le T\le10^5),表示测试用例数量。

对于每个测试用例:

第一行包含两个整数 H,WH,W(1≤H,W≤1091\le H,W\le10^9),表示矩形板两个坐标轴方向上的边长。

接下来三行,第 ii 行包含两个整数 hi,wih_i,w_i(1≤hi≤H1\le h_i\le H,1≤wi≤W1\le w_i\le W),表示第 ii 张卡片的边长。其中 hih_i 对应第一个坐标方向,wiw_i 对应第二个坐标方向,不允许交换二者来单独旋转卡片。

原题没有额外的跨用例边长总和限制。

输出格式

对于每个测试用例,输出一行一个整数,表示符合要求的不同放置方案数对 109+710^9+7 取模的结果。

原样例 1

5
2 2
1 1
1 1
1 1
2 2
1 1
1 2
1 2
2 2
1 1
1 2
2 1
2 2
1 2
1 2
1 2
2 2
1 2
1 2
2 1
0
8
4
6
4

原样例 2

4
1 3
1 1
1 2
1 3
1 4
1 1
1 2
1 3
1 5
1 1
1 2
1 3
1 6
1 1
1 2
1 3
6
12
14
6

原样例 3

1
1000000000 1000000000
1 1
1 1
1000000000 1000000000
2401