Descripción

Entre sus juguetes, Octavia tiene "N" cubos de tamaño idéntico. Los cubos pueden ser diferentes en peso, pero también pueden tener pesos iguales. Octavia disfruta colocando sus cubos en una secuencia larga y jugando por muchas horas con ellos, luego ella comenzó a preguntarse sobre la cantidad de secuencias diferentes que puede obtener.

La secuencia de cubos es representada por ~N~ enteros, donde cada uno de ellos representa al peso del cubo correspondiente en la secuencia inicial. Octavia puede escoger dos cubos adyacentes e intercambiarlos si y solo si el peso combinado no es mayor que el entero ~K~. Octavia puede repetir la operación e intercambiar cualquier par de cubos adyacentes con peso combinado no mayor a K las veces que quiera. Dos secuencias pueden ser consideradas diferentes si su secuencia de pesos son diferentes.

Por ejemplo si tenemos ~4~ ~cubos~ con pesos ~[1, 2, 1, 3]~ y ~K = 3~. Hay ~3~ posibles secuencias de cubos que podemos obtener. La primera de ellas es la secuencia inicial.

Para obtener la segunda secuencia, podemos intercambiar los cubos de la posición ~2~ y ~3~ de la secuencia inicial y obtener la secuencia ~[1, 1, 2, 3]~. Nótese que no podemos intercambiar los cubos de la secuencia ~1~ y ~3~ porque no son adyacentes. Tampoco podemos intercambiar ~3~ y ~4~ porque su peso total es ~4~, y ~K = 3~. Nosotros podemos obtener la última secuencia intercambiando los dos primeros cubos en la secuencia inicial y obtener ~[2, 1, 1, 3]~.

Tarea

Escribe un programa que resuelva la tarea que Sasha te da.

Entrada

Hay ~2~ enteros en la primera línea: ~N~ - el número de cubos y ~K~ - y el máximo peso total de dos cubos adyacentes que pueden ser intercambiados. Luego hay ~N~ enteros positivos ~w_i~, en la segunda línea de la entrada, correspondientes a los pesos de la secuencia inicial.

Salida

Una única línea con el número posible de secuencias que Octavia puede obtener, módulo ~1 000 000 007~.

Restricciones

• 1 ≤ N ≤ 300000
• 1 ≤ w_i, K ≤ 1000000000

SubTareas

No Restricciones Puntos

1 | ~N \le 7~ | Los pesos son diferentes | puntos ~7~

2 | ~N \le 100~ | Los pesos son diferentes | puntos ~23~

3 | ~N \le 1000~ | Los pesos son diferentes | puntos ~15~

4 | ~N \le 1000~ | - | puntos ~15~

5 | ~N \le 100000~ | Los pesos son diferentes | puntos ~21~

6 | ~N \le 300000~ | - | puntos ~19~

Los puntos de cada subtarea se entregaran solo si pasa todos sus casos.

Ejemplo #1 de Entrada

4 5
1 2 1 3

Ejemplo #1 de Salida

12

Explicación del Ejemplo

En el enunciado del problema.

Ejemplo #2 de Entrada

5 4
4 3 1 5 2

Ejemplo #2 de Salida

2

Explicación del Ejemplo #2

Nosotros podemos solo intercambiar los cubos con pesos ~1~ y ~3~, y la respuesta es ~2~, y dos posibles secuencias son ~[4, 3, 1, 5, 2]~ y ~[4, 1, 3, 5, 2]~.