题目描述

给你一个整数$n$，代表有$n$对数$x,y$,你最开始有一个整数$ans = 1$,接下来你有$n$次操作。

每次操作你可以任意选择一对数，对于每一对数你只可以操作一次 ，操作内容是对于你选择的$x_i,y_i$,$ans = ans * x_i + y_i$

输出最大的$ans$,为了防止答案过大,最终答案对$10^9 + 7$取模

输入格式

一个整数 $n$ $(1 \le n \le 10^5)$ 接下来$n$行每行一对数 $x_i,y_i$ $(1 \le x_i,y_i \le 10^6)$

输出格式

最大的$ans$

样例

2
1 2
3 4

13

提示

第一次操作选择第一对 $ans = ans * x_1 + y_1$ $ans = 1 * 1 + 2 = 3$ 第二次操作选择第二对 $ans = ans * x_2 + y_2$ $ans = 3 * 3 + 4 = 13$

来源

2022 HGNU-SWUT暑假联合集训