#P17944. Hiking Trip

Hiking Trip

Hiking Trip

从西到东有 nn 处景点,高度依次为 h1,…,hnh_1,\ldots,h_n。选择一个区间 [l,r][l,r] 徒步,满足以下条件时称该区间合法:

  • 不存在 l<i<rl<i<r 使 hi−1>hi<hi+1h_{i-1}>h_i<h_{i+1},即内部没有严格山谷;
  • 对所有 l≤i<rl\le i<r,都有 hi≠hi+1h_i\ne h_{i+1},即相邻景点不等高。

有些高度已知。每个未知高度分别独立、均匀地从 [1,m][1,m] 中的整数选取。求合法区间数量的期望,对 109+710^9+7 取模。

输入格式

第一行是测试用例数 tt,1≤t≤1051\le t\le10^5。

每组用例第一行包含 n,mn,m。第二行包含 nn 个整数 h1,…,hnh_1,\ldots,h_n:hi=−1h_i=-1 表示未知,否则表示确定的高度。

  • 1≤n≤1061\le n\le10^6,所有用例的 ∑n≤107\sum n\le10^7;
  • 1≤m≤1091\le m\le10^9;
  • hi=−1h_i=-1 或 1≤hi≤m1\le h_i\le m。

输出格式

每组用例输出一个整数,表示期望对 109+710^9+7 取模的结果。分数按分母的模逆元解释。

单点区间总是合法;严格上升、严格下降以及先严格上升后严格下降的区间都可能合法。

样例 1

10
4 4
1 4 2 3
3 3
-1 2 -1
4 2
-1 -1 -1 1
4 3
1 -1 -1 3
5 5
-1 2 -1 4 -1
6 4
2 -1 1 -1 -1 1
5 5
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 13 -1 10 -1 -1 -1 -1 12 -1 3 -1 -1 -1 18
8
666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617