小卡和纸牌

题目背景

小卡最近迷上了纸牌，现在他找你来玩一个纸牌游戏。

题目描述

小卡一共有 $n$ 张纸牌，每张纸牌有正、反两面，每一面都写有一个整数，第 $i$ 张牌的正面是 $a_i$，背面是 $b_i$。

现在小卡让你选择每张牌是正面朝上还是反面朝上。选定之后，你的得分就是所有朝上的数字的乘积。

当然，你想让你的最终得分最高。请你输出你可能获得的最高的最终得分，这个结果可能很大，所以你只需要输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行一个正整数 $n$，表示纸牌的张数。

第二行 $n$ 个正整数 $a_i$，表示纸牌正面的数字。

第三行 $n$ 个正整数 $b_i$，表示纸牌背面的数字。

输出格式

一行一个正整数，表示你能获得的最大的分数。

样例 #1

样例输入 #1

3
1 2 3
-1 -2 -3

样例输出 #1

6

样例 #2

样例输入 #2

4
1 2 -4 4
-2 -3 3 -5

样例输出 #2

120

样例 #3

样例输入 #3

1
-1
-2

样例输出 #3

1000000006

提示

对于 $30\%$ 的数据，保证 $1\le n \le 10,-10 \le a_i,b_i \le 10 $，你必须通过这部分所有的数据，才能得到 30 分。

对于另外 $30\%$ 的数据，保证所有的数字都是正数，你必须通过这部分所有的数据，才能得到这 30 分。

对于 $100\%$ 的数据，保证 $1\le n\le 10^5,-10^{9}\le a_i \le 10^9,-10^9 \le b_i \le 10^9$，且 $a_i,b_i \ne 0$。

Solution

贪心

将正反面数字符号不同的纸牌翻面能改变累乘结果的符号，乘积必为负时全部选择绝对值较小的一面。能使乘积为正时贪心选择绝对值较大的一面，若最终乘积不为正则将一张正反面数字符号不同的纸牌翻面。

令 $mul=\prod\limits_{i=1}^n a_i$，其中 $a_i$ 是纸牌 $i$ 绝对值较大的一面的数字，$b_i$ 是另一面的数字。翻面使得乘积变为 $mul \times \dfrac{b_i}{a_i}$。找到正反面数字符号不同的纸牌中 $\left| \dfrac{b_i}{a_i} \right|$ 最大的一张翻面即可。