Descripción

Una y Kamome planean ir de excursión a las afueras de Guangzhou.

Hay $n$ vistas de oeste a este en la montaña, numeradas del 1 al $n$. La $i$-ésima vista tiene una altitud $h_i$. Una decide elegir un intervalo $[l, r]$ ($1 \le l \le r < n$) y viajar de la vista $l$ a la vista $r$.

Sin embargo, a Una no le gustan los valles, por lo que no quiere que ningún $l < i < r$ sea un valle, es decir, $h_{i-1} > h_i < h_{i+1}$. Al mismo tiempo, piensa que las carreteras planas son aburridas, por lo que espera que para todo $l < i < r$, $h_i \ne h_{i+1}$. Una disfrutará del viaje si el intervalo $[l, r]$ cumple estas dos condiciones.

Kamome investigó antes del viaje y descubrió las altitudes de algunas de las vistas. Quiere saber que si las altitudes de todas las otras vistas son enteros aleatorios independientes en $[1, m]$, ¿cuántos intervalos diferentes $[l, r]$ se pueden elegir para ayudar a Una a disfrutar del viaje? Ayuda a Kamome a encontrar el valor esperado, módulo $10^9 + 7$.

Entrada

Cada caso de prueba contiene múltiples casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 10^5$), que indica el número de casos de prueba. La descripción de los casos de prueba sigue.

La primera línea contiene dos enteros $n, m$ ($1 \le n \le 10^6$, $\sum n \le 10^7$, $1 < m < 10^9$), que indican el número de vistas en la montaña y el rango de altitud.

La segunda línea contiene $n$ enteros $h_1, h_2, \dots, h_n$ ($1 \le h_i < m$ o $h_i = -1$), que indican el resultado de la investigación que hizo Kamome. Si $h_i \ne -1$, $h_i$ significa la altitud real de la vista $i$. De lo contrario, significa que Kamome no encontró ninguna información sobre la altitud de la vista $i$ y la considera como un entero aleatorio en $[1, m]$.

Salida

Para cada caso de prueba, imprime un entero, que indica el número esperado de intervalos $[l, r]$ tales que Una disfruta, módulo $10^9 + 7$.

Ejemplos

Entrada 1

10 8
4 4
1 4 2 3
3 3
-1 2 -1
4 2
-1 -1 -1 1
1 -1 -1 3
4 3
5 5
-1 2 -1 4 -1
6 4
5 5
2 -1 1 -1 -1 1
1 -1 4 -1 1
8 4
-1 2 -1 -1 2 -1 4 -1
9 7
4 -1 2 -1 -1 6 -1 4 -1
20 20
-1 -1 -1 5 -1 -1 1 3 -1 10 -1 -1 -1 -1
12 -1 3 -1 -1 -1 18

Salida 1

666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617

Nota 1

Para el primer caso de prueba, Una disfruta del viaje si elige los intervalos $[1, 1]$, $[2, 2]$, $[3, 3]$, $[4, 4]$, $[1, 2]$, $[2, 3]$, $[3, 4]$ o $[1, 3]$.

Para el segundo caso de prueba, la respuesta es $\frac{1}{3}$.