問題文
帕肯王国的形状是一个无限扩大的二维平面。在帕肯王国 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
- 所有输入均为整数
小課題
- (50 点) N=1
- (50 点) N\leq 10,\ M\leq2000
- (100 点) M\leq100
- (200 点) a_i≠a_j\ (i≠j)
- (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,\ 2 破坏真实的道路。1 第二个房子也是 2 第二个房子也不在路上。
- 1 破坏真实的道路。1 第二个房子也是 2 第二个房子也是 2 它位于主干道上。
- 2 破坏真实的道路。1 第二个房子是 1 虽然是在主干道上,2 第二个房子不在路上。
- 1 书籍也不会破坏道路。1 第二个房子是 1,\ 2 位于主干道上,2 第二个房子也是 2 它位于主干道上。
此示例是一个小作业。 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 约束。
作者: 企鹅人