题目描述

小 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)$ 取模后的结果。

5
1 2 3 4 5
100 200 300 400 500

18060

样例 2

见附加文件中 [food2.in](file:food2.in) 和 [food2.ans](file:food2.ans)。

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

样例 3

见附加文件中 [food3.in](file:food3.in) 和 [food3.ans](file:food3.ans)。

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

样例 4

见附加文件中 [food4.in](file:food4.in) 和 [food4.ans](file:food4.ans)。

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

样例 5

见附加文件中 [food5.in](file:food5.in) 和 [food5.ans](file:food5.ans)。

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

样例 6

见附加文件中 [food6.in](file:food6.in) 和 [food6.ans](file:food6.ans)。

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

样例 7

见附加文件中 [food7.in](file:food7.in) 和 [food7.ans](file:food7.ans)。

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

样例 8

见附加文件中 [food8.in](file:food8.in) 和 [food8.ans](file:food8.ans)。

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

样例 9

见附加文件中 [food9.in](file:food9.in) 和 [food9.ans](file:food9.ans)。

数据范围与提示

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

测试点编号	$n \le$	特殊性质
$1$	$10$	DE
$2$		E
$3$		AE
$4$		E
$5$	$20$	DE
$6$		E
$7$
$8$
$9$	$2000$	D
$10$		无
$11$
$12$
$13$	$5 \times {10}^5$	BD
$14$		B
$15$		C
$16$
$17$	${10}^5$	无
$18$
$19$	$5 \times {10}^5$
$20$

特殊性质 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$。