UnaとKamomeは、広州郊外でのハイキングを計画しています。山には西から東に$n$の展望地点があり、$1$から$n$まで番号が付けられています。地点$i$の標高は$h_i$です。Unaは区間$[l, r]$（$1 \le l \le r < n$）を選び、地点$l$から地点$r$まで移動することにしました。

しかし、Unaは谷が好きではないので、$l < i < r$となるどの$i$も谷になっていてほしくありません。つまり、$h_{i-1} > h_i < h_{i+1}$となることを避けたいのです。同時に、平坦な道は退屈だと考えているため、すべての$l < i < r$について$h_i \ne h_{i+1}$であることを望んでいます。Unaは、区間$[l, r]$がこれら2つの条件を満たす場合にその旅を気に入ります。

Kamomeはハイキングの前に調査を行い、いくつかの展望地点の標高を調べました。彼女は、残りのすべての地点の標高が$[1, m]$の範囲で独立にランダムな整数である場合、Unaが旅を気に入るような異なる区間$[l, r]$がいくつ存在するかを知りたいと思っています。Kamomeが期待値を、$10^9 + 7$を法として求めるのを助けてください。

入力

各テストは複数のテストケースを含みます。最初の行には整数$t$（$1 \le t \le 10^5$）が含まれ、テストケースの数を示します。その後、テストケースの説明が続きます。

各テストケースの最初の行には、2つの整数$n, m$（$1 \le n \le 10^6$、$\sum n \le 10^7$、$1 < m < 10^9$）が含まれ、山の展望地点の数と標高の範囲を示します。

2行目には$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]$のランダムな整数とみなします。

出力

各テストケースについて、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 -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]$を選ぶと旅を気に入ります。

2番目のテストケースでは、答えは$\frac{1}{3}$です。