T303996 「DPOI-1」炊事员的鸡汤

你可以选择看一遍[《激战江南》](https://www.bilibili.com/bangumi/play/ss20249?spm_id_from=333.337.0.0)，也可以选择做这道题。 老冯是一名潜伏多年的炊事员。 王大队长今天请大伙吃饭，要求炊事员老冯炖鸡汤。因为老冯是间谍，需要在鸡汤里面下毒，用毒杀害他人。 但是他需要用鸡汤和毒药配出最佳的配方，不能太明显也不能没有毒效。

现在老冯有 $n$ 种配方瓶，其中对于**一份**第 $i$ 种配方，鸡汤和毒药分别有 $x_i, y_i$ 毫升。 现在你需要帮他调配鸡汤，具体地： - 设 $a_i \geq 0$ 表示第 $i$ 中配方使用的份数。**老冯必须使用整数份。** - 老冯希望 $a$ **单调不降**。 - 老冯还希望鸡汤混合毒药后的净含量为 $m$ 毫升，即 $m = \displaystyle\sum_{i = 1}^n a_i (x_i + y_i)$。 - 老冯还希望鸡汤与毒药的质量比为 $o : p$，即 $\displaystyle\sum_{i = 1}^n a_i x_i : \displaystyle\sum_{i = 1}^n a_i y_i = o : p$。 请你快速求出**有多少种满足条件的调配方案**。由于结果可能很大，你只需要求出结果对 $10^9 + 7$ 取模的值。

**本题有多组测试数据。** 第一行，一个整数 $T$，表示数据组数。 对于每组数据： 第一行，四个整数 $n, m, o, p$； 接下来 $n$ 行，其中第 $i$ 行两个整数 $x_i, y_i$。

对于每组数据： 一行，一个整数，表示所求的值。

#### 样例 #1 解释 对于第一组数据，可以证明唯一的合法方案为 $a = [1, 1]$。 对于第二组数据，可以证明没有合法方案。 #### 样例 #2 解释 该样例满足测试点 $17 \sim 20$ 的限制。 #### 数据范围 | 测试点编号 | $n, m \leq$ | 特殊条件 | | :------: | :------: | :------: | | $1 \sim 2$ | $10$ | 无 | | $3 \sim 4$ | $30$ | 无 | | $5 \sim 6$ | $50$ | 无 | | $7 \sim 8$ | $100$ | 无 | | $9 \sim 10$ | $300$ | 无 | | $11 \sim 12$ | $500$ | 无 | | $13 \sim 14$ | $10^3$ | 无 | | $15 \sim 16$ | $2 \times 10^3$ | $x_i = y_i = 1$ | | $17 \sim 20$ | $2 \times 10^3$ | 无 | 对于 $100\%$ 的数据，$1 \leq T \leq 5$，$1 \leq n \leq 2 \times 10^3$，$2 \leq m \leq 2 \times 10^3$，$1 \leq o, p, x_i, y_i \leq m$。