← 返回题目列表

Codeforces · 1748/E

E. 又一个数组计数问题

中文机器翻译题面 查看原题

段 $$$[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]$$$.