Una 和 Kamome 计划去广州郊区徒步旅行。 山上有 $n$ 个观景点，从西到东编号为 $1$ 到 $n$。第 $i$ 个观景点的高度为 $h_i$。Una 决定选择一个区间 $[l, r]$（$1 \le l \le r < n$），并从第 $l$ 个观景点旅行到第 $r$ 个观景点。

然而，Una 不喜欢山谷，所以她不希望任何 $l < i < r$ 是一个山谷，即 $h_{i-1} > h_i < h_{i+1}$。同时，她认为平坦的道路很无聊，所以她希望对于所有 $l < i < r$，都有 $h_i \ne h_{i+1}$。如果区间 $[l, r]$ 满足这两个条件，Una 就会感到高兴。

Kamome 在徒步旅行前做了一些研究，并找到了其中一些观景点的高度。她想知道，如果所有其他观景点的高度是 $[1, m]$ 范围内的独立随机整数，有多少个不同的区间 $[l, r]$ 可以让 Una 感到高兴。帮助 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$）。如果 $h_i \ne -1$，则表示观景点 $i$ 的实际高度。否则，表示 Kamome 没有找到关于观景点 $i$ 高度信息，并将其视为 $[1, m]$ 范围内的随机整数。

输出格式

对于每组测试数据，打印一个整数，表示 Una 感到高兴的区间 $[l, r]$ 的期望数量，模 $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 18
-1 3 -1 -1 -1 1 18

输出

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}$。