Una и Kamome планируют поход в пригороде Гуанчжоу. В горах с запада на восток расположено $n$ смотровых точек, пронумерованных от $1$ до $n$. Высота точки $i$ равна $h_i$. Una решает выбрать отрезок $[l, r]$ ($1 \le l \le r < n$) и пройти от точки $l$ до точки $r$.

Однако Una не любит долины, поэтому она не хочет, чтобы какая-либо точка $i$ с $l < i < r$ была долиной. То есть она хочет избежать ситуации $h_{i-1} > h_i < h_{i+1}$. В то же время она считает плоскую дорогу скучной, поэтому требует, чтобы для всех $l < i < r$ выполнялось $h_i \ne h_{i+1}$. Una считает поход удачным, если отрезок $[l, r]$ удовлетворяет этим двум условиям.

Перед походом Kamome провела исследование и выяснила высоты некоторых смотровых точек. Она хочет узнать, сколько различных отрезков $[l, r]$ таковы, что Una останется довольна походом, если высоты всех остальных точек являются независимыми случайными целыми числами в диапазоне $[1, m]$. Помогите Kamome найти математическое ожидание по модулю $10^9 + 7$.

Входные данные

Каждый тест содержит несколько тестовых случаев. Первая строка содержит целое число $t$ ($1 \le t \le 10^5$) — количество тестовых случаев. Далее следуют описания тестовых случаев.

Первая строка каждого тестового случая содержит два целых числа $n, m$ ($1 \le n \le 10^6$, $\sum n \le 10^7$, $1 < m < 10^9$) — количество смотровых точек в горах и диапазон высот.

Вторая строка содержит $n$ целых чисел $h_1, h_2, \dots, h_n$ ($1 \le h_i < m$ или $h_i = -1$) — результаты исследования Kamome. Если $h_i \ne -1$, то $h_i$ — фактическая высота точки $i$. В противном случае Kamome ещё не нашла информацию о высоте точки $i$ и считает её случайным целым числом из $[1, m]$.

Выходные данные

Для каждого тестового случая выведите количество отрезков $[l, r]$, которые понравятся Una, в виде математического ожидания по модулю $10^9 + 7$.

Примеры

Входные данные 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

Выходные данные 1

8
666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617

Примечание

В первом тестовом случае Una останется довольна, если выберет отрезки $[1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3], [3, 4]$ или $[1, 3]$.

Во втором тестовом случае ответ равен $\frac{1}{3}$.