E - 老朽化対策 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

パ研王国は無限に広がる二次元平面の形をしています。パ研王国には N 本の道路と M 軒の家があり、i\ (1\leq i\leq N) 本目の道路は y=a_ix+b_i の式で表される直線の形をしていて、また i\ (1\leq i\leq M) 軒目の家は座標 (x_i,\ y_i) に位置しています。

パ研王国では道路の老朽化が問題になっており、0 本以上の道路を選んで取り壊すことになりました。道路を 0 本以上選んで取り壊す方法は 2^N 通りありますが、それぞれについて 1 本以上の壊されていない道路の上にある家の軒数を数え、その総和を 10^9+7 で割った余りを求めてください。

制約

  • 1\leq N,\ M\leq10^5
  • -5×10^4\leq a_i\leq5×10^4
  • 0\leq b_i\leq5×10^4
  • 0\leq x_i,\ y_i\leq5×10^4
  • 入力は全て整数

小課題

  1. (50 点) N=1
  2. (50 点) N\leq 10,\ M\leq2000
  3. (100 点) M\leq100
  4. (200 点) a_i≠a_j\ (i≠j)
  5. (400 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます。

\(N\) \(M\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(︙\)
\(a_N\) \(b_N\)
\(x_1\) \(y_1\)
\(x_2\) \(y_2\)
\(︙\)
\(x_M\) \(y_M\)

出力

総和を 10^9+7 で割った余りを求めてください。出力の最後に改行を忘れないでください。

入力例1

2 2
1 2
2 1
1 3
2 5

出力例1

5

道路の壊され方には以下の 4 通りがあります。

  1. 1,\ 2 本目の道路を壊す。1 軒目の家も 2 軒目の家も道路上にない。
  2. 1 本目の道路を壊す。1 軒目の家も 2 軒目の家も 2 本目の道路上にある。
  3. 2 本目の道路を壊す。1 軒目の家は 1 本目の道路上にあるが、2 軒目の家は道路上にない。
  4. 1 本も道路を壊さない。1 軒目の家は 1,\ 2 本目の道路上にあり、2 軒目の家も 2 本目の道路上にある。
これら全てにおける、問題文中の条件を満たす家の軒数の総和は 5 となるため、5 を出力します。

このサンプルは小課題 2,\ 3,\ 4,\ 5 の制約を満たします。

入力例2

2 5
1 3
1 3
2 5
2 5
2 5
2 5
2 5

出力例2

15

このサンプルは小課題 2,\ 3,\ 5 の制約を満たします。

入力例3

4 3
1 5
2 3
-1 11
3 2
1 5
3 8
2 7

出力例3

36

このサンプルは小課題 2,\ 3,\ 4,\ 5 の制約を満たします。

Writer : penguinman