AT_pakencamp_2020_day2_e 老朽化対策

Description

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day2/tasks/pakencamp_2020_day2_e 配点 : $ 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 $ で割った余りを求めてください。

Input Format

入力は以下の形式で標準入力から与えられます。 ``` $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$ ```

Output Format

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

Explanation/Hint

### 小課題 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 $ 点) 追加の制約はない．