El granjero John intenta producir su famosa leche OohMoo para venderla con ganancias. Tiene ~N~ botellas que intenta llenar. Cada botella contiene inicialmente una cantidad de leche ~m_i~. Cada día, toma ~A~ botellas y las llena con una unidad de leche.

Desafortunadamente, el granjero Nhoj, competidor del granjero John en el negocio de la leche OohMoo, conoce el proceso de producción del granjero John y tiene un plan para perjudicarlo. Cada día, después de que el granjero John llene sus ~A~ botellas, el granjero Nhoj robará sigilosamente una unidad de leche de cada una de ~B~ botellas diferentes que no estén vacías. Para pasar desapercibido, el granjero Nhoj elige ~B~ de forma que sea estrictamente menor que ~A~, para que sea menos probable que el granjero John lo descubra.

Después de ~D~ días, el granjero John venderá su leche OohMoo. Si una botella contiene ~M~ unidades de leche, se venderá por ~M^2~ moonies.

Sea ~P~ la ganancia única tal que el granjero John puede garantizar que obtendrá al menos ~P~ de ganancia independientemente del comportamiento del granjero Nhoj, y el granjero Nhoj puede garantizar que el granjero John obtendrá como máximo P de ganancia independientemente de su comportamiento. Imprima el valor de P módulo 10⁹ + 7.

Entrada

• La primera línea de la entrada contiene ~N~ y ~D~, donde ~N~ es el número de botellas y ~D~ es el número de días transcurridos.
• La segunda línea de la entrada contiene ~A~ y ~B~, que representan la cantidad de unidades de leche que el granjero John llena y el granjero Nhoj roba, respectivamente.
• La tercera línea de la entrada contiene ~N~ enteros separados por espacios, ~m_i~, que representan la cantidad inicial de leche en cada botella.

Salida

Imprimir el valor de ~P~ módulo ~10^9+7~.

Restricciones

• ~1 \leq N \leq 10^5~
• ~1 \leq A \leq N~
• ~0 \leq B < A~
• ~0 \leq m_i \leq 10^9~
• ~1 \leq D \leq 10^9~

Ejemplo #1 de Entrada

5 4
4 2
4 10 8 10 10

Ejemplo #1 de Salida

546

El primer día, el granjero John pudo añadir leche a la segunda, tercera, cuarta y quinta botella. Luego, el granjero Nhoj pudo extraer leche de la segunda y cuarta botella.

Por lo tanto, la nueva cantidad de leche en cada botella es:

~[4,10,8,10,10]\rightarrow [4,11,9,11,11] \rightarrow [4,10,9,10,11]~.

Después de cuatro días, la cantidad de leche en cada botella podría ser: ~[4,10,8,10,10] \rightarrow [4,10,9,10,11] \rightarrow [4,10,10,11,11] \rightarrow [4,11,11,11,11] \rightarrow [4,11,11,12,12]~.

La cantidad total de moonies que el granjero John ganaría en esta situación es ~42+112+112+122+122=546~. Se puede demostrar que este es el valor de ~P~.

Ejemplo #2 de Entrada

10 5
5 1
1 2 3 4 5 6 7 8 9 10

Ejemplo #2 de Salida

777

Ejemplo #3 de Entrada

5 1000000000
3 1
0 1 2 3 4

Ejemplo #3 de Salida

10

Asegúrese de que la salida sea ~P~ módulo ~10^9+7~.

USACO 2025 US Open Contest, Gold Problem 3. OohMoo Milk.