Little A loves to eat.
Little A has $n$ portions of food in front of her, where the $i$-th portion has parameters $a_i$ and $b_i$. Little A can eat these $n$ portions of food in any order. When she eats the $i$-th portion, she can choose to either multiply her weight by $a_i$ or add $b_i$ to her weight. Each portion of food can be eaten exactly once.
Little A's initial weight is $1$. Find the maximum weight she can achieve after eating all $n$ portions of food. The answer may be very large, so you only need to output the result modulo $({10}^9 + 7)$.
Note: You need to maximize the weight and then take the maximum value modulo $({10}^9 + 7)$, rather than maximizing the weight modulo $({10}^9 + 7)$.
Input
The first line contains an integer $n$, representing the number of food portions. 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$, representing the parameters for each portion of food.
Output
Output a single integer representing the maximum weight Little A can achieve, modulo $({10}^9 + 7)$.
Examples
Input 1
5
1 2 3 4 5
100 200 300 400 500Output 1
18060Note 1
The following sequence achieves the maximum weight:
- Eat the first portion and choose to add $100$ to the weight; the weight becomes $101$.
- Eat the second portion and choose to add $200$ to the weight; the weight becomes $301$.
- Eat the third portion and choose to multiply the weight by $3$; the weight becomes $903$.
- Eat the fourth portion and choose to multiply the weight by $4$; the weight becomes $3612$.
- Eat the fifth portion and choose to multiply the weight by $5$; the weight becomes $18060$.
Input 2
See the provided files. This test case satisfies $n \le 10$ and special property E.
Input 3
See the provided files. This test case satisfies $n \le 20$ and special property E.
Input 4
See the provided files. This test case satisfies $n \le 2000$.
Input 5
See the provided files. This test case satisfies special property A.
Input 6
See the provided files. This test case satisfies special property C.
Input 7
See the provided files. This test case satisfies special property D.
Input 8
See the provided files. This test case satisfies special property B.
Input 9
See the provided files.
Subtasks
For $100\%$ of the test data, $1 \le n \le 5 \times {10}^5$ and $1 \le a_i, b_i \le {10}^6$.
| Test Case ID | $n \le $ | Special Property |
|---|---|---|
| $1$ | $10$ | DE |
| $2$ | $10$ | E |
| $3$ | $10$ | AE |
| $4$ | $10$ | E |
| $5$ | $20$ | DE |
| $6$ | $20$ | E |
| $7$ | $20$ | E |
| $8$ | $20$ | E |
| $9$ | $2000$ | D |
| $10$ | $2000$ | None |
| $11$ | $2000$ | None |
| $12$ | $2000$ | None |
| $13$ | $5 \times {10}^5$ | BD |
| $14$ | $5 \times {10}^5$ | B |
| $15$ | $5 \times {10}^5$ | C |
| $16$ | $5 \times {10}^5$ | C |
| $17$ | ${10}^5$ | None |
| $18$ | ${10}^5$ | None |
| $19$ | $5 \times {10}^5$ | None |
| $20$ | $5 \times {10}^5$ | None |
- 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 in $[1, {10}^6]$.
- Special property D: $a_i \ge 2$.
- Special property E: $a_i \le 4$.