商品の入出荷 1 VB(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
同じ種類の商品について、以下のような 2n 個の入出荷情報が与えられます。
・ i 番目の出荷情報は整数の組 (a_i, b_i) で表される。
・ a_i = 1 のとき、商品が入荷されることを表す。
・ a_i = 2 のとき、商品が出荷されることを表す。
・ 入荷または出荷される商品の個数は常に 1 である。
・ b_i は、その商品の入荷または出荷の時刻を表す。
・ 入荷情報および出荷情報はそれぞれちょうど n 個ずつ存在する。
与えられた入出荷情報をもとに、各商品の入荷と出荷をすべて組み合わせる方法が何通りかあるか求めてください。
ここで、各商品の入荷と出荷を組み合わせる方法とは、整数 1 から 2n までの並べ替え p = (p_1, p_2, ..., p_{2n}) であって、
a_{p_2k} = 1 かつ a_{p_{2k+1}} = 2 (1 ≦ k ≦ n) を満たし、かつ b_{p_{2k}} < b_{p_{2k+1}} を満たすもののことを指します。
例えば、入力例 1 では、時刻 1, 2 に入荷があり、時刻 3, 4 に出荷があります。
よって、それぞれの時刻の情報の番号を順に 1, 2, 3, 4 とすると、
(1, 3), (2, 4) および (1, 4), (2, 3) の 2 通りの組み合わせが条件を満たします。
ただし、答えは非常に大きくなることがあるため、1000000007 = 10^9 + 7 で割った余りを求めてください。
なお、入荷時刻が出荷時刻よりも真に早いか同じ場合のみ、入荷と出荷の組み合わせが可能であるものとします。
- 入力される値
-
n
a_1 b_1
a_2 b_2
...
a_2n b_2n
・ 1 行目に、入出荷情報の個数 (の半分) を表す整数 n が与えられます。
・ 続く 2n 行に、整数 a_i, b_i が半角スペース区切りで与えられます。a_i が 1 の場合は入荷、2 の場合は出荷を表します。b_i は商品の入荷または出荷の時刻を表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、答えを 10^9 + 7 で割った余りを整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 500
・ 1 ≦ a_i ≦ 2 (1 ≦ i ≦ 2n)
・ a_i = 1 となる i はちょうど n 個存在する
・ a_i = 2 となる i はちょうど n 個存在する
・ 1 ≦ b_i ≦ 1000 = 10^3
・ b_i ≠ b_j (1 ≦ i, j ≦ 2n, i ≠ j) (与えられる入荷時刻および出荷時刻はすべて異なる)
- 入力例1
-
2
1 1
1 2
2 3
2 4
- 出力例1
-
2
- 入力例2
-
3
2 500
1 100
1 200
2 300
1 600
2 400
- 出力例2
-
0
