样例下载

问题描述

有 $n$ 个一次函数，第 $i$ 个函数是 $f_i(x)=a_ix+b_i$。

容易发现，一次函数和一次函数的复合仍然是一次函数：

$$f_i\left(f_j(x)\right)=a_i\left(a_jx+b_j\right)+b_i $$

现在给定 $x_0\ge0$，我们希望重新排列这 $n$ 个一次函数，使得它们依次复合之后在 $x_0$ 处的值最大。换句话说，你要找到一个 $1$ ~ $n$ 的排列 $\{p_i\}$，使得 $f_{p_1}(f_{p_2}(\dots f_{p_n}(x_0)\dots))$ 的值最大。

你只需要输出复合函数最终可以得到的最大值。

答案可能很大，你只需要输出答案 mod $(10^9+7)$。

输入格式

输入的第一行包含两个整数 $n,x_0$，分别代表函数的个数与 $x_0$ 的值。

之后的 $n$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 个函数为 $f_i(x)=a_ix+b_i$。

输出格式

输出包含一行一个整数，表示答案 mod $(10^9+7)$。

输入输出样例

输入

2 2
1 1
2 3

输出

9

数据规模与约定

对于 $20\%$ 的数据，$n\le 2$；

对于 $40\%$ 的数据，$n\le 9$；

对于 $60\%$ 的数据，$n\le 1000$；

对于另外 $10\%$ 的数据，保证所有$a_i=1$；

对于 $100\%$的数据，$n\le100000$，$1\le a_i,b_i\le 10$，$0\le x_0\le 9$。