Autor: Vicente Opazo

Tiempo límite: 3 segundos

Memoria límite: 256 megabytes

A Valentina le encanta estar a la moda. Para armar sus atuendos dispone de \(N\) tipos de prendas (por ejemplo: camisas, pantalones, zapatos, etc.). Para cada tipo de prenda \(i\), existen \(A_{i}\) opciones distintas que ella puede elegir.

Un día Valentina ganó el primer premio de una rifa: la posibilidad de obtener \(K\) prendas adicionales, pudiendo escoger libremente de qué tipo serán. Con estas prendas extra, Valentina busca maximizar la cantidad total de atuendos distintos que podrá formar.

Un atuendo se compone de exactamente una prenda de cada tipo, y por lo tanto el número de atuendos posibles es el producto de las cantidades disponibles de cada tipo de prenda. Valentina quiere elegir de qué tipos serán sus \(K\) prendas adicionales para que este producto sea lo más grande posible.

Como el número puede ser muy grande, se pide calcular el resultado módulo \(10^{9} + 7\).

Entrada

La primera línea contiene dos enteros \(1 \le N\le 10^{6}\) y \(0 \le K\le 10^{9}\), el número de tipos de prendas y la cantidad de prendas adicionales que Valentina puede obtener.

La segunda línea contiene \(N\) enteros \(1 \le A_{1}, A_{2}, \ldots , A_{N}\le 10^{9}\), donde \(A_{i}\) representa cuántas opciones de la \(i\)-ésima prenda existen inicialmente.

Salida

Imprimir un único entero: la cantidad máxima de atuendos distintos que Valentina puede formar, módulo \(10^{9} + 7\).

Ejemplos

Entrada 1

3 2
2 3 1

Salida 1

18

Entrada 2

4 0
5 2 3 2

Salida 2

60

Nota

• Para el primer caso de prueba el producto inicial es \(2 \cdot 3 \cdot 1 = 6\). Valentina podría sumar sus dos prendas extra al segundo tipo (que tenía 3 opciones), de tal forma de conseguir \(2 \cdot 5 \cdot 1 = 10\) combinaciones. Sin embargo, una mejor estrategía sería sumar una prenda extra al primer tipo y otra prenda extra al tercer tipo, de tal forma de conseguir \(3 \cdot 3 \cdot 2 = 18\) combinaciones. Se puede demostrar que no se puede conseguir un resultado mejor.
• En el segundo caso de prueba no puede sumar ninguna prenda extra, así que el resultado es simplemente \(5 \cdot 2 \cdot 3 \cdot 2 = 60\)