Mô tả bài toán

Una và Kamome lên kế hoạch đi bộ đường dài ở vùng ngoại ô Quảng Châu. Có $n$ điểm ngắm cảnh từ tây sang đông trên núi, được đánh số từ 1 đến $n$. Điểm thứ $i$ có độ cao $h_i$. Una quyết định chọn một khoảng $[l, r]$ ($1 \le l \le r < n$) và di chuyển từ điểm thứ $l$ đến điểm thứ $r$.

Tuy nhiên, Una không thích thung lũng, vì vậy cô ấy không muốn bất kỳ $l < i < r$ nào là một thung lũng, tức là $h_{i-1} > h_i < h_{i+1}$. Đồng thời, cô ấy nghĩ rằng đường bằng phẳng thì nhàm chán, vì vậy cô ấy hy vọng rằng với mọi $l < i < r$, $h_i \ne h_{i+1}$. Una sẽ thích chuyến đi nếu khoảng $[l, r]$ thỏa mãn hai điều kiện này.

Kamome đã nghiên cứu trước chuyến đi bộ đường dài và tìm ra độ cao của một số điểm ngắm cảnh. Cô ấy muốn biết nếu độ cao của tất cả các điểm còn lại là các số nguyên ngẫu nhiên độc lập trong $[1, m]$, có bao nhiêu khoảng $[l, r]$ khác nhau có thể được chọn để giúp Una thích chuyến đi. Hãy giúp Kamome tìm giá trị kỳ vọng, theo modulo $10^9 + 7$.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^5$), cho biết số lượng trường hợp thử nghiệm. Tiếp theo là mô tả các trường hợp thử nghiệm.

Dòng đầu tiên chứa hai số nguyên $n, m$ ($1 \le n \le 10^6$, $\sum n \le 10^7$, $1 < m < 10^9$), cho biết số lượng điểm ngắm cảnh trên núi và phạm vi độ cao.

Dòng thứ hai chứa $n$ số nguyên $h_1, h_2, \dots, h_n$ ($1 \le h_i < m$ hoặc $h_i = -1$), cho biết kết quả nghiên cứu của Kamome. Nếu $h_i \ne -1$, $h_i$ có nghĩa là độ cao thực tế của điểm $i$. Ngược lại, nó có nghĩa là Kamome chưa tìm thấy thông tin nào về độ cao của điểm $i$ và coi nó là một số nguyên ngẫu nhiên trong $[1, m]$.

Dữ liệu ra

Đối với mỗi trường hợp thử nghiệm, hãy in ra một số nguyên, cho biết số lượng kỳ vọng các khoảng $[l, r]$ sao cho Una thích chuyến đi, theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

8
666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617

Ghi chú

Đối với trường hợp thử nghiệm đầu tiên, Una thích chuyến đi nếu cô ấy chọn các khoảng $[1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3], [3, 4]$ hoặc $[1, 3]$.

Đối với trường hợp thử nghiệm thứ hai, câu trả lời là $\frac{1}{3}$.