题目描述

给定整数 $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)$ 时，这些正方形不会严格重叠。