G. 溶液配制 Ⅱ
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小 H 有 $$$n$$$ 瓶溶液，含有相同的两种溶质，第 $$$i$$$ 瓶溶液的两种溶质浓度分别为 $$$(v_i,w_i)$$$ 。

他想用这 $$$n$$$ 瓶溶液来配置一些新溶液。他可以选择 $$$n$$$ 瓶中的任意瓶以任意的比例混合来得到一瓶新的溶液。对于某种特定浓度的目标溶液，他想知道有多少种溶液的选择方案可以配置得到该目标溶液。

一种选择方案可以看成 $$$n$$$ 的 $$$2^n$$$ 个子集中的一个。若目标两种溶质浓度为 $$$(x,y)$$$ ，$$$n$$$ 的某个子集 $$$S=\{a_1,a_2,a_3...a_m\}$$$ 可以配置得到浓度为 $$$(x,y)$$$ 的溶液，当且仅当存在非负实数 $$$p_1,p_2,p_3...p_m$$$ ，使得 $$$\sum_{i=1}^{m}p_i=1$$$ 且 $$$\sum_{i=1}^{m}p_iv_{a_i}=x$$$ ， $$$\sum_{i=1}^{m}p_iw_{a_i}=y$$$ 。由于选择方案可能很多请告诉他方案数模 $$$10^9+7$$$ 的余数。

Input

第一行两个正整数 $$$n$$$，$$$q$$$ ，表示有 $$$n$$$ 瓶溶液，$$$q$$$ 个询问 $$$(1 \le n,q \le 2000)$$$。

接下来 $$$n$$$ 行，每行两个小数 $$$v_i$$$ $$$w_i$$$ 表示第 $$$i$$$ 瓶溶液的浓度，格式固定两位整数位，三位小数位。

接下来 $$$q$$$ 行，每行两个小数 $$$x_i$$$ $$$y_i$$$ 表示第 $$$i$$$ 次询问的目标溶液浓度，格式固定两位整数位，三位小数位。

Output

输出 $$$q$$$ 行，每行一个整数表示方案数模 $$$10^9+7$$$ 的余数。

Example
Input
4 4
00.000 00.000
20.000 00.000
00.000 20.000
20.000 20.000
10.000 10.000
00.000 00.000
30.000 20.500
00.001 00.000
Output
7
8
0
4