Maximizing Expression Value

Given ( n ) non-negative integers ( A_i ), you are allowed to insert the symbols ( \tt{+} ), ( \tt{*} ), ( \tt{(} ), and ( \tt{)} ) between them (without changing their order) to form a valid arithmetic expression. Determine the maximum possible value of the resulting expression. Since the answer can be very large, output the result modulo (10^9+7).

Note that you may insert the symbols arbitrarily as long as the final expression is valid.

inputFormat

The input consists of two lines. The first line contains a single integer ( n ). The second line contains ( n ) non-negative integers ( A_1, A_2, \dots, A_n ) separated by spaces.

outputFormat

Output a single integer representing the maximum possible value of the expression modulo (10^9+7).

sample

3
1 2 3

9