Problem Description

Little A really likes eating.

There are $n$ portions of food in front of Little A. The $i$-th portion has parameters $a_i$ and $b_i$. Little A can eat these $n$ portions in any order. When she eats the food numbered $i$, she may choose to multiply her weight by $a_i$, or add $b_i$ to her weight. Each portion of food must be eaten exactly once.

Little A's initial weight is $1$. Please find the maximum weight she can reach after eating all $n$ portions of food. The answer may be very large; you only need to output it modulo $({10}^9 + 7)$.

Note: You need to maximize the weight first, and then take the maximum value modulo $\bm{({10}^9 + 7)}$, rather than maximizing the value of (weight modulo $\bm{({10}^9 + 7)}$).

Input Format

The first line contains an integer $n$, the number of portions of food. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, and the third line contains $n$ integers $b_1, b_2, \ldots, b_n$, describing the parameters of each portion.

Output Format

Output one integer, the maximum weight Little A can obtain modulo $({10}^9 + 7)$.

5
1 2 3 4 5
100 200 300 400 500

18060

Hint

[Sample Explanation #1]

The following plan can achieve the maximum weight:

• Eat the first portion and choose to increase the weight by $100$, making the weight $101$.
• Eat the second portion and choose to increase the weight by $200$, making the weight $301$.
• Eat the third portion and choose to multiply the weight by $3$, making the weight $903$.
• Eat the fourth portion and choose to multiply the weight by $4$, making the weight $3612$.
• Eat the fifth portion and choose to multiply the weight by $5$, making the weight $18060$.

[Sample #2]

See food/food2.in and food/food2.ans in the attachment.

This sample satisfies $n \le 10$ and special property E.

[Sample #3]

See food/food3.in and food/food3.ans in the attachment.

This sample satisfies $n \le 20$ and special property E.

[Sample #4]

See food/food4.in and food/food4.ans in the attachment.

This sample satisfies $n \le 2000$.

[Sample #5]

See food/food5.in and food/food5.ans in the attachment.

This sample satisfies special property A.

[Sample #6]

See food/food6.in and food/food6.ans in the attachment.

This sample satisfies special property C.

[Sample #7]

See food/food7.in and food/food7.ans in the attachment.

This sample satisfies special property D.

[Sample #8]

See food/food8.in and food/food8.ans in the attachment.

This sample satisfies special property B.

[Sample #9]

See food/food9.in and food/food9.ans in the attachment.

[Constraints]

For $100\%$ of the testdata, $1 \le n \le 5 \times {10}^5$, $1 \le a_i, b_i \le {10}^6$.

Special property A: $a_i = 1$.
Special property B: $a_i \ge b_i$.
Special property C: $a_i, b_i$ are generated independently and uniformly at random within $[1, {10}^6]$.
Special property D: $a_i \ge 2$.
Special property E: $a_i \le 4$.

Translated by ChatGPT 5