J - ピラミッド - 2D編
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
伊織ちゃんのマイブームはピラミッドである。
伊織ちゃんはピラミッドを題材にした問題を思いついた。しかし、その問題は既出の問題だということが発覚し、伊織ちゃんは拗ねてしまった。そして、伊織ちゃんは別の問題を考えることにした。
段数が無限である 2 次元のピラミッドを考える。上から i (1 ≦ i) 段目の左から j (1 ≦ j ≦ i) 個目の石を石 (i,j) と呼ぶことにする。石 (A,B) と石 (C,D) を取ることを考える。石 (i,j) を取るためには、石 (i-1,j-1) と石 (i-1,j) を先に取らなければならない(i-1 < 1 または j-1 < 1 または j > i となる場合は石が最初から存在しないため取る必要はない)。石 (A,B) と石 (C,D) を取る方法であって、取る石の個数が最小となるような取り方は何通りあるだろうか?ただし、取り方は石を取る順番によって区別され、石を取る順番が異なる時 2 つの取り方は違う取り方であるということにする。また、同じタイミングで 2 つ以上の石を取ることはできない。
入力
入力は以下の形式で標準入力から与えられる。
T A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 : A_T B_T C_T D_T
- 1 行目には、テストケースの個数を表す整数 T (1 ≦ T ≦ 300,000) が与えられる。
- 2 行目からの T 行には、各テストケースの情報が与えられる。このうち i (1 ≦ i ≦ T) 行目には、4 つの整数 A_i (1 ≦ A_i ≦ 10^6), B_i (1 ≦ B_i ≦ A_i), C_i (1 ≦ C_i ≦ 10^6), D_i (1 ≦ D_i ≦ C_i) が与えられる。これは、i 番目テストケースにおける A,B,C,D の値を表す。ただし、A_i ≠ C_i または B_i ≠ D_i が成り立つことが保証されている。また、取る必要のある石の個数が 10^6 個を超えないことも保証されている。
出力
出力は T 行からなる。このうち i (1 ≦ i ≦ T) 行目には、i 番目のテストケースの答えを 10^9+7 で割った余りを出力せよ。出力の末尾にも改行を入れること。
入力例1
6 2 1 2 2 1 1 1000000 1000000 3 2 5 3 5 2 4 3 2015 55 1700 1300 100 50 1000 500
出力例1
2 1 42 252 926737422 143485143
1 個目のテストケースでは以下の 2 通りの取り方がある。
- 石 (1,1)、石 (2,2)、石 (2,1) の順に取る。
- 石 (1,1)、石 (2,1)、石 (2,2) の順に取る。