Malditos unos P84469

Dada una secuencia de naturales $x_1 \dots x_n$ entre 0 y 9, escoged como operarlos mediante sumas y productos, poniendo los paréntesis que queráis, de manera que el resultado final sea el máximo posible. Por ejemplo, para la secuencia $$1 \enspace 3 \enspace 2 \enspace 0 \enspace 9 \enspace 1 \enspace 1 \enspace 3 \enspace 1 \enspace 5$$ el máximo resultado posible es $$(1 + 3) * (2 + 0) * 9 *(1 + 1) * (3 + 1) * 5 = 2880 \; .$$ Fijáos que no está permitido cambiar el orden de los números dados, ni unirlos entre si para formar números de dos o más dígitos.

Entrada

La entrada consiste en diversos casos. Cada caso comienza con $n$, seguida de $n$ números entre 0 y 9. Asumid $1 \le n \le 10^4$.

Salida

Para cada caso, escribid el máximo resultado posible módulo $10^9 + 7$.

Puntuación

• Test1:

  Resolver casos donde todas las $x_i$ están entre 2 y 9, como los del ejemplo 1.

• Test2:

  Resolver casos donde $n \le 10$ y el resultado sin hacer módulos no sería superior a $10^9$, como los del ejemplo 2.

• Test3:

  Resolver casos donde $n \le 20$ y el resultado sin hacer módulos no sería superior a $10^{18}$, como los del ejemplo 3.

• Test4:

  Resolver casos de todo tipo.