Énoncé

Una et Kamome prévoient de faire une randonnée dans la banlieue de Guangzhou. Il y a $n$ points de vue d'ouest en est dans la montagne, numérotés de 1 à $n$. Le $i$-ème point de vue a une altitude $h_i$. Una décide de choisir un intervalle $[l, r]$ ($1 \le l \le r < n$) et de voyager du $l$-ème point de vue au $r$-ème point de vue.

Cependant, Una n'aime pas les vallées, donc elle ne veut pas que pour tout $l < i < r$, $h_{i-1} > h_i < h_{i+1}$. En même temps, elle pense que les routes plates sont ennuyeuses, donc elle espère que pour tout $l < i < r$, $h_i \ne h_{i+1}$. Una appréciera le voyage si l'intervalle $[l, r]$ satisfait ces deux conditions.

Kamome a fait quelques recherches avant le voyage de randonnée et a découvert les altitudes de certains points de vue. Elle veut savoir que si les altitudes de tous les autres points de vue sont des entiers aléatoires indépendants dans $[1, m]$, combien d'intervalles $[l, r]$ différents peuvent être choisis pour aider Una à apprécier le voyage. Aidez Kamome à trouver la valeur attendue, modulo $10^9 + 7$.

Entrée

Chaque cas de test contient plusieurs cas de test. La première ligne contient un entier $t$ ($1 \le t \le 10^5$), indiquant le nombre de cas de test. La description des cas de test suit.

La première ligne contient deux entiers $n, m$ ($1 \le n \le 10^6$, $\sum n \le 10^7$, $1 < m < 10^9$), indiquant le nombre de points de vue dans la montagne et la plage d'altitudes.

La deuxième ligne contient $n$ entiers $h_1, h_2, \dots, h_n$ ($1 \le h_i < m$ ou $h_i = -1$), indiquant le résultat de la recherche que Kamome a faite. Si $h_i \ne -1$, $h_i$ signifie l'altitude réelle du point de vue $i$. Sinon, cela signifie que Kamome n'a trouvé aucune information sur l'altitude du point de vue $i$ et la considère comme un entier aléatoire dans $[1, m]$.

Sortie

Pour chaque cas de test, imprimez un entier, indiquant le nombre attendu d'intervalles $[l, r]$ tels qu'Una apprécie le voyage, modulo $10^9 + 7$.

Exemples

Entrée 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

Sortie 1

666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617

Remarque 1

Pour le premier cas de test, Una apprécie le voyage si elle choisit les intervalles $[1, 1]$, $[2, 2]$, $[3, 3]$, $[4, 4]$, $[1, 2]$, $[2, 3]$, $[3, 4]$ ou $[1, 3]$. Pour le deuxième cas de test, la réponse est $\frac{1}{3}$.