段 $$$[l 上最左边最大值的位置; r]$$$ 数组 $$$x = [x_1, x_2, \ldots, x_n]$$$ 是满足 $$$l \le i \le r$$$ 且 $$$x_i = \max(x_l, x_{l+1}, \ldots, x_r)$$$ 的最小整数 $$$i$$$。
给定一个数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,长度为 $$$n$$$。查找满足以下条件的长度为 $$$n$$$ 的整数数组 $$$b = [b_1, b_2, \ldots, b_n]$$$ 的数量:
- $$$1 \le b_i \le m$$$ 对于所有 $$$1 \le i \le n$$$;
- 对于所有整数对 $$$1 \le l \le r \le n$$$,段 $$$[l 上最左边最大值的位置; r]$$$ 数组 $$$b$$$ 等于段 $$$[l 上最左边最大值的位置; r]$$$ 数组 $$$a$$$。
由于答案可能非常大,因此打印其对 $$$10^9+7$$$ 取模的余数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n,m \le 2 \cdot 10^5$$$, $$$n \cdot m \le 10^6$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$) — 数组 $$$a$$$。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,打印一个整数 - 满足语句条件的数组 $$$b$$$ 的数量,以 $$$10^9+7$$$ 为模。
示例
输入 #1
4 3 3 1 3 2 4 2 2 2 2 2 6 9 6 9 6 9 6 9 9 100 10 40 20 20 100 60 80 60 60
输出 #1
8 5 11880 351025663
注意
在第一个测试用例中,以下 $$$8$$$ 数组满足语句中的条件:
- $$$[1,2,1]$$$;
- $$$[1,2,2]$$$;
- $$$[1,3,1]$$$;
- $$$[1,3,2]$$$;
- $$$[1,3,3]$$$;
- $$$[2,3,1]$$$;
- $$$[2,3,2]$$$;
- $$$[2,3,3]$$$.
在第二个测试用例中,以下 $$$5$$$ 数组满足语句中的条件:
- $$$[1,1,1,1]$$$;
- $$$[2,1,1,1]$$$;
- $$$[2,2,1,1]$$$;
- $$$[2,2,2,1]$$$;
- $$$[2,2,2,2]$$$.