小 A 很喜欢吃东西。

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

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

注意：你需要最大化体重并将该最大值对 \bm{({10}^9 + 7)} 取模，而非最大化体重对 \bm{({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】

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

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

对于 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。

辽宁省选