#P18459. Three Rectangles
Three Rectangles
Three Rectangles
题目描述
平面上有一块边与坐标轴平行的矩形板,其左下角为 ,右上角为 。
给定三张矩形卡片,需要将它们完整地放在矩形板内,使三张卡片共同覆盖整块矩形板,并求不同放置方案的数量。卡片不能旋转或翻转,每张卡片的边必须与坐标轴平行,所有顶点坐标都必须是整数。卡片之间允许重叠。
当且仅当存在一张卡片在两个方案中的位置不同,两个方案才被视为不同。因此三张卡片有各自的编号,即使尺寸相同,也不能将它们当作无法区分的卡片。
由于答案可能很大,请输出答案对 取模的结果。
输入格式
第一行包含一个整数 (),表示测试用例数量。
对于每个测试用例:
第一行包含两个整数 (),表示矩形板两个坐标轴方向上的边长。
接下来三行,第 行包含两个整数 (,),表示第 张卡片的边长。其中 对应第一个坐标方向, 对应第二个坐标方向,不允许交换二者来单独旋转卡片。
原题没有额外的跨用例边长总和限制。
输出格式
对于每个测试用例,输出一行一个整数,表示符合要求的不同放置方案数对 取模的结果。
原样例 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