AT_maximum_cup_2023_g イノシシ対策

S君は $ xy $ 平面上の $ (X,Y) $ にある畑で農業を始めることにしました。 しかし、平面上には $ N $ 頭のイノシシがいて畑を荒らそうとしています。 $ i $ 番目のイノシシは $ (x_i,y_i) $ に棲んでいます。 S君が対処法を求めて役所に相談したところ、 $ M $ 個の計画を提案されました。 $ i $ 番目の計画は直線 $ y = a_i x + b_i $ 上に柵を設置するというもので、実行する場合 $ 2^{i-1} $ 円かかります。 畑を守るには $ i=1,2,\ldots,N $ すべてに対して、 $ (X,Y) $ と $ (x_i,y_i) $ を結ぶ線分(端点含む)とある柵に対応する直線が交点を持つ必要があります。 計画を $ 0 $ 個以上選んで実行し、畑を守るのに必要な金額の最小値を $ C $ 円とします。 $ C $ を $ (10^9+7) $ で割った余りを求めてください。 ただし、どのように計画を選んでも畑を守ることが出来ない場合、代わりに `-1` と出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X $ $ Y $ $ x_1 $ $ y_1 $ $ \vdots $ $ x_N $ $ y_N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_M $ $ b_M $

答えを出力せよ。

### Sample Explanation 1 $ 1,3 $ 番目の計画を選んで実行するのが最適で、 $ C= 2^{1-1} + 2^{3-1} = 5 $ であるため、 $ 5 $ を $ (10^9+7) $ で割った余りである $ 5 $ が期待される出力です。 ### Sample Explanation 2 同じ座標に複数のイノシシが棲んでいる場合や、(必要な金額を除いて)同じ計画が存在する場合があります。 ### Constraints - $ 1 \leq N,M \leq 2 \times 10^5 $ - $ -10^9 \leq X,Y,x_i,y_i,a_i,b_i \leq 10^9 $ - $ (X,Y) \neq (x_i,y_i) $ - 入力はすべて整数