M-最大化仿射变换_2025年广东工业大学新生赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

有一个变量 $x$ ，初始时 $x = 0$ 。

给定 $n$ 个操作，第 $i$ 个操作定义了一个仿射变换，形式为：

$x := a_i x + b_i$

其中 $:=$ 为赋值号， $a_i$ 和 $b_i$ 均为非负整数。

你需要将这 $n$ 个操作安排一个执行顺序，并依次执行。目标是使得所有操作执行完毕后，最终 $x$ 的值达到最大。

由于最终 $x$ 的值可能会很大，请输出这个最大值对 $10^9+7$ 取模后的结果，注意不是取模后的最大值，而是对最大值取模。

第一行输入一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例数量。

每个测试用例格式如下：

第一行包含一个正整数 $n$ （ $1\leq n \leq 10^6$ ），表示操作的总数。
接下来的 $n$ 行，第 $i$ 行包含两个非负整数 $a_i$ , $b_i$ （ $0 \leq a_i, b_i \leq 10^9$ ），表示第 $i$ 个操作的参数。

保证所有测试用例的 $n$ 之和不超过 $10^6$ 。

输出一个整数，表示在所有可能的执行顺序中，最终 $x$ 的最大值对 $10^9+7$ 取模后的结果。

示例1

复制

复制