/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
整数 N, A, B が与えられます。
辺の長さが N の白い正方形を座標平面の (0,0), (N,0), (0,N), (N,N) に 4 頂点が重なるように置きます。
次に、この白い正方形の内部または周上に収まるように、辺の長さが A の青い正方形と辺の長さが B の赤い正方形を 1 つずつ置きます。
ただし、正方形のどの辺も x 軸または y 軸と平行に置かれている必要があります。
また、青い正方形と赤い正方形の各頂点は格子点上に置かれている必要があります。
赤い正方形の内部と青い正方形の内部が重ならないように置く方法の数を 1,000,000,007 で割ったあまりを求めてください。
1 つの入力につき、T 個のテストケースに答えてください。
制約
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^9
- 1 \leq A \leq N
- 1 \leq B \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。入力の 1 行目は以下のとおりである。
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) のときは赤い正方形と青い正方形の内部が重なっていないことに注意してください。
Score : 400 points
Problem Statement
Given are integers N, A, and B.
We will place a white square whose side is of length N on the coordinate plane so that the vertices are at (0, 0), (N, 0), (0, N), and (N, N).
Then, we will place a blue square whose side is of length A and a red square whose side is of length B so that these squares are inside the white square (including its boundary).
Here, each side of these squares must be parallel to the x- or y-axis.
Additionally, each vertex of red and blue squares must be at an integer point.
Find the number of ways to place red and blue squares so that they do not strictly overlap (they may share boundary with each other), modulo 1,000,000,007.
Solve this problem for T test cases in each input file.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^9
- 1 \leq A \leq N
- 1 \leq B \leq N
- All values in input are integers.
Input
Input is given from Standard Input as follows. The first line of input is in the format below:
T
Then, T test cases follow, each of which is in the format below:
N A B
Output
For each test case, print the number of ways to place red and blue squares so that they do not strictly overlap, modulo 1,000,000,007. Use one line for each test case.
Sample Input 1
3 3 1 2 4 2 2 331895368 154715807 13941326
Sample Output 1
20 32 409369707
For example, in the first test case, there are 9 ways to place the blue squares and 4 ways to place the red squares, ignoring overlap.
Wherever we place the red square, there are 4 ways to place the blue square so that it strictly overlaps with the red square.
Thus, there are 9 \times 4 - 4 \times 4 = 20 ways to place red and blue squares so that they do not strictly overlap.
Note that the squares may share boundary with each other. For example, when the bottom-left vertices of blue and red squares are (0, 0) and (0, 1), respectively, the squares do not strictly overlap.