← 返回题目列表

AtCoder · hhkb2020_d

D. 正方形

中文机器翻译题面 查看原题

分数: 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)分别,方块并不严格重叠。