#3737. 「LNOI2022」吃

题目描述

小 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

输出

18060

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

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

样例 2-9

见附加文件中 food2.in 到 food9.in 和对应的 .ans 文件。

数据范围与提示

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

特殊性质说明：

• 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$