题目描述

blg 遇到了一个难题,你能帮帮他吗？

有一个数组 $A$ 长度为 $n$，从里面选出 $m(m≥1)$ 个数进行连乘，其最大值和最小值分别是多少？

输入格式

第一行一个整数 $n$，表示数字的个数。

接下来一行有 $n$ 个整数，第 $i$ 个整数表示数组元素 $a_i$。

输出格式

输出最小的连乘积和最大的连乘积。

由于结果可能很大，请输出答案除以 $10^9+7$ 的余数。

测试样例

5
1 3 5 7 9

1 945

2
-3 6

-18 6

1
-4

-4 -4

3
-2 -3 -4

-24 12

样例说明

样例1：选一个 $1$ 可获得最小值，全选可获得最大值。

样例2：全选可获得最小值，只选 $6$ 可获得最大值。

数据规模说明

对 $40\%$ 数据，$1≤n≤20$。

对 $100\%$ 数据，$1≤n≤2×10^5$，$|a_i|≤10^9$。