Problem Description

Score: $ 800 $ points

The Kingdom of Paken extends infinitely in a two-dimensional plane. The kingdom has $ N $ roads and $ M $ houses. The $ i $-th road ($1 \leq i \leq N$) is represented by the line equation $ y = a_i x + b_i $, and the $ i $-th house ($1 \leq i \leq M$) is located at coordinates $ (x_i, y_i) $.

In the Kingdom of Paken, the aging of roads has become a problem, and it has been decided to demolish zero or more roads. There are $ 2^N $ ways to choose zero or more roads to demolish. For each of these ways, count the number of houses that are on at least one undemolished road, and find the sum of these counts modulo $ 10^9 + 7 $.

Input Format

The input is given from the standard input in the following 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

Find the sum modulo $ 10^9 + 7 $. Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

2 2
1 2
2 1
1 3
2 5

Sample Output #1

5

Sample Input #2

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

Sample Output #2

15

Sample Input #3

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

Sample Output #3

36

Notes/Hints

Subtasks

1. ($ 50 $ points) $ N = 1 $
2. ($ 50 $ points) $N \leq 10, M \leq 2000$
3. ($ 100 $ points) $M \leq 100$
4. ($ 200 $ points) $a_i \neq a_j\ (i \neq j)$
5. ($ 400 $ points) No additional constraints.

见题面 Input 部分

见题面 Output 部分