题目描述

SIMO 最近喜欢玩一款肉鸽闯关游戏

SIMO 的这款肉鸽游戏有 $n$ 个关卡可以选择，第 $i$ 关通过后有两种属性的卡片可以 $a_i$ 和 $b_i$ 选择。这款游戏和其他肉鸽游戏的区别在于，SIMO 可以按照任意顺序通过这 $n$ 个关卡。当他通过编号为 $i$ 的关卡时，他可以选择将自己的战斗力值乘以 $a_i$ 或者将自己的战斗力值加上 $b_i$。每个关卡的奖励领取完后就不能在次领取了。

SIMO 的初始能力值为 $1$，请求出他闯完 $n$ 个关卡后能达到的最大能力值。答案可能很大，你只需要输出其对 (${10}^9 + 7$) 取模后的结果。

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

输入格式

第一行输入一个整数 $n$ 表示关卡的数量。（$1\leq n \leq 5 \times 10^5$）

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个关卡的能力翻倍值参数 $a_i$。($1\leq a_i \leq 10^6$)

第三行 $n$ 个整数 $b_1, b_2, \ldots , b_n$，表示每个关卡的能力增加值参数 $b_i$。($1\leq b_i \leq 10^6$)

输出格式

输出一个整数，表示SIMO 可以得到的最大能力值对 (${10}^9 + 7$) 取模后的结果。

样例描述

输入样例1

4
1 2 3 4 
4 3 2 1

输出样例1

120

输入样例2

10
4 4 4 1 2 3 1 2 2 4
851105 155483 119600 708518 1 434595 269435 1 1 182032

输出样例2

8549334

提示

第一个样例中以下方案可以达到最大能力值：

• 通过第一关并选择将能力值增加 $4$ ，能力值变为 $5$ ；

• 通过第二关并选择将能力值翻倍 $2$ ，能力值变为 $10$ ；

• 通过第三关并选择将能力值翻倍 $3$ ，能力值变为 $30$ ；

• 通过第四关并选择将能力值翻倍 $4$ ，能力值变为 $120$ ；