問題文

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 と出力してください。

制約

• 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)
• 入力はすべて整数

入力例 1

3 3 1 1
2 4
3 9
-5 10
-4 8
3 -3
-7 7

出力例 1

5

1,3 番目の計画を選んで実行するのが最適で、C= 2^{1-1} + 2^{3-1} = 5 であるため、5 を (10^9+7) で割った余りである 5 が期待される出力です。

入力例 2

2 2 0 0
10 3
10 3
5 2
5 2

出力例 2

-1

同じ座標に複数のイノシシが棲んでいる場合や、(必要な金額を除いて)同じ計画が存在する場合があります。