分数: 400 点
问题陈述
给定的是整数 N, A,和 B.
我们将放置一个边长为 的白色正方形 N 在坐标平面上,使得顶点位于 (0, 0), (N, 0), (0, N),和 (N, N).
然后,我们将放置一个边长为 的蓝色正方形 A 和一个边长为 的红色正方形 B 使这些方块位于白色方块内部(包括其边界)。
这里,这些正方形的每条边都必须平行于 x- 或 y- 轴。
此外,红色和蓝色方块的每个顶点必须位于整数点。
找到放置红色和蓝色方块的方法数量,使它们不严格重叠(它们可以彼此共享边界),模 1,000,000,007.
解决这个问题 每个输入文件中的 T 测试用例。
约束
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^9
- 1 \leq A \leq N
- 1 \leq B \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入给出,如下所示。第一行输入格式如下:
T
然后, T 测试用例如下,每个测试用例的格式如下:
N A B
输出
对于每个测试用例,打印放置红色和蓝色方块的方法数量,以便它们不会严格重叠,模数 1,000,000,007。 每个测试用例使用一行。
示例输入 1
3 3 1 2 4 2 2 331895368 154715807 13941326
示例输出 1
20 32 409369707
例如,在第一个测试用例中,有 9 放置蓝色方块和 4 放置红色方块的方法,忽略重叠。
无论我们将红色方块放在哪里,都有 4 放置蓝色方块使其与红色方块严格重叠的方法。
因此,有 9 \times 4 - 4 \times 4 = 20 放置红色和蓝色方块以使它们不严格重叠的方法。
请注意,正方形可能彼此共享边界。例如,当蓝色和红色方块的左下顶点是 (0, 0) 和 (0, 1)分别,方块并不严格重叠。