P8365 [LNOI2022] Eat

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)}$).**

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 one integer, the maximum weight Little A can obtain modulo $({10}^9 + 7)$.

**[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$. | Test Point ID | $n \le $ | Special Properties | |:-:|:-:|:-:| | $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 within $[1, {10}^6]$. Special property D: $a_i \ge 2$. Special property E: $a_i \le 4$. Translated by ChatGPT 5