Una i Kamome planują pieszą wycieczkę na przedmieściach Kantonu. W górach znajduje się $n$ punktów widokowych, ponumerowanych od $1$ do $n$ z zachodu na wschód. Wysokość punktu $i$ wynosi $h_i$. Una postanowiła wybrać przedział $[l, r]$ ($1 \le l \le r < n$) i przejść od punktu $l$ do $r$.

Jednak Una nie lubi dolin, więc nie chce, aby żadne $i$ takie, że $l < i < r$, było doliną. Innymi słowy, chce uniknąć sytuacji $h_{i-1} > h_i < h_{i+1}$. Jednocześnie uważa, że płaska droga jest nudna, więc chce, aby dla wszystkich $l < i < r$ zachodziło $h_i \ne h_{i+1}$. Una polubi podróż, jeśli przedział $[l, r]$ spełnia te dwa warunki.

Kamome przed wędrówką przeprowadziła badanie i poznała wysokości niektórych punktów widokowych. Chce wiedzieć, ile różnych przedziałów $[l, r]$ spodoba się Unie, jeśli wysokości wszystkich pozostałych punktów są niezależnymi losowymi liczbami całkowitymi z zakresu $[1, m]$. Pomóż Kamome obliczyć wartość oczekiwaną modulo $10^9 + 7$.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^5$) oznaczającą liczbę przypadków testowych. Następnie podane są opisy przypadków.

W pierwszym wierszu każdego przypadku testowego znajdują się dwie liczby całkowite $n, m$ ($1 \le n \le 10^6$, $\sum n \le 10^7$, $1 < m < 10^9$) oznaczające liczbę punktów widokowych oraz zakres wysokości.

Drugi wiersz zawiera $n$ liczb całkowitych $h_1, h_2, \dots, h_n$ ($1 \le h_i < m$ lub $h_i = -1$) – wyniki badań Kamome. Jeśli $h_i \ne -1$, oznacza to rzeczywistą wysokość punktu $i$. W przeciwnym razie Kamome nie znalazła jeszcze informacji o wysokości punktu $i$ i traktuje ją jako losową liczbę całkowitą z zakresu $[1, m]$.

Wyjście

Dla każdego przypadku testowego wypisz wartość oczekiwaną liczby przedziałów $[l, r]$ spodobających się Unie, modulo $10^9 + 7$.

Przykład

Wejście 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

Wyjście 1

8
666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617

Uwagi

W pierwszym przypadku testowym Una polubi podróż, jeśli wybierze przedziały $[1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3], [3, 4]$ lub $[1, 3]$.

W drugim przypadku testowym odpowiedź wynosi $\frac{1}{3}$.