問題文

$N$ 項の式 $A_1\ op_1\ A_2,\ldots,op_{N-1}\ A_N$ を考えます。$A_i$ は正整数、$op_i$ は '+' または '×' の記号です。

$N$ と $A_1,\ A_2,\ldots,A_N$ が与えられるので、適切に $op_i$ に記号を代入することで式の結果を最大化し、最大値を出力してください。

これは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

演算の優先順位は通常の式同様、掛け算 → 足し算の順に高いです。

入力

$N$
$A_1\ A_2\ldots A_N$

• $2≤N≤2×10^5$
• $1≤A_i≤10^9$
• 入力は全て整数

出力

演算結果の最大値を $10^9+7$ で割った余りを出力してください。

サンプル

4
2 1 3 1

7

5
5 1 4 2 3

120

7
11032 193029 8284 13828 73476 1391 10

518962052