QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 4221. 吃

Statistics

小 A 很喜欢吃东西。

小 A 面前有 $n$ 份食物,第 $i$ 份有参数 $a_i$ 和 $b_i$。小 A 可以按照任意顺序吃掉这 $n$ 份食物。当她吃掉编号为 $i$ 的食物时,她可以选择将自己的体重乘以 $a_i$ 或者将自己的体重加上 $b_i$。每份食物只能吃恰好一次。

小 A 的初始体重为 $1$,请求出她吃完 $n$ 份食物后能达到的最大体重。答案可能很大,你只需要输出其对 $({10}^9 + 7)$ 取模后的结果。

注意:你需要最大化体重并将该最大值对 $\boldsymbol{({10}^9 + 7)}$ 取模,而非最大化体重对 $\boldsymbol{({10}^9 + 7)}$ 取模的结果。

输入格式

第一行输入一个整数 $n$ 表示食物的数量。第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$,第三行 $n$ 个整数 $b_1, b_2, \ldots, b_n$,表示每份食物的参数。

输出格式

输出一个整数,表示小 A 可以得到的最大体重对 $({10}^9 + 7)$ 取模后的结果。

样例数据

样例 1 输入

5
1 2 3 4 5
100 200 300 400 500

样例 1 输出

18060

样例 1 解释

以下方案可以达到最大体重:

  • 吃掉第一份食物并选择将体重增加 $100$,体重变为 $101$;
  • 吃掉第二份食物并选择将体重增加 $200$,体重变为 $301$;
  • 吃掉第三份食物并选择将体重乘 $3$,体重变为 $903$;
  • 吃掉第四份食物并选择将体重乘 $4$,体重变为 $3612$;
  • 吃掉第五份食物并选择将体重乘 $5$,体重变为 $18060$。

样例 2

见下发文件。

该组样例满足 $n \le 10$ 和特殊性质 E。

样例 3

见下发文件。

该组样例满足 $n \le 20$ 和特殊性质 E。

样例 4

见下发文件。

该组样例满足 $n \le 2000$。

样例 5

见下发文件。

该组样例满足特殊性质 A。

样例 6

见下发文件。

该组样例满足特殊性质 C。

样例 7

见下发文件。

该组样例满足特殊性质 D。

样例 8

见下发文件。

该组样例满足特殊性质 B。

样例 9

见下发文件。

子任务

对于 $100 \%$ 的测试数据,$1 \le n \le 5 \times {10}^5$,$1 \le a_i, b_i \le {10}^6$。

测试点编号 $n \le $ 特殊性质
$1$ $10$ DE
$2$ $10$ E
$3$ $10$ AE
$4$ $10$ E
$5$ $20$ DE
$6$ $20$ E
$7$ $20$ E
$8$ $20$ E
$9$ $2000$ D
$10$ $2000$
$11$ $2000$
$12$ $2000$
$13$ $5 \times {10}^5$ BD
$14$ $5 \times {10}^5$ B
$15$ $5 \times {10}^5$ C
$16$ $5 \times {10}^5$ C
$17$ ${10}^5$
$18$ ${10}^5$
$19$ $5 \times {10}^5$
$20$ $5 \times {10}^5$
  • 特殊性质 A:$a_i = 1$。
  • 特殊性质 B:$a_i \ge b_i$。
  • 特殊性质 C:$a_i, b_i$ 在 $[1, {10}^6]$ 内独立均匀随机生成。
  • 特殊性质 D:$a_i \ge 2$。
  • 特殊性质 E:$a_i \le 4$。