CF1748E.Yet Another Array Counting Problem

The position of the leftmost maximum on the segment $[l; r]$ of array $x = [x_1, x_2, \ldots, x_n]$ is the smallest integer $i$ such that $l \le i \le r$ and $x_i = \max(x_l, x_{l+1}, \ldots, x_r)$.

You are given an array $a = [a_1, a_2, \ldots, a_n]$ of length $n$. Find the number of integer arrays $b = [b_1, b_2, \ldots, b_n]$ of length $n$ that satisfy the following conditions:

• $1 \le b_i \le m$ for all $1 \le i \le n$;
• for all pairs of integers $1 \le l \le r \le n$, the position of the leftmost maximum on the segment $[l; r]$ of the array $b$ is equal to the position of the leftmost maximum on the segment $[l; r]$ of the array $a$.

Since the answer might be very large, print its remainder modulo $10^9+7$.

数组 $x = [x_1, x_2, \ldots, x_n]$ 在区间 $[l; r]$ 上的最左最大值位置，是指满足 $l \le i \le r$ 且 $x_i = \max(x_l, x_{l+1}, \ldots, x_r)$ 的最小整数 $i$。

给定一个长度为 $n$ 的数组 $a = [a_1, a_2, \ldots, a_n]$。请计算满足以下条件的长度为 $n$ 的整数数组 $b = [b_1, b_2, \ldots, b_n]$ 的个数：

• 对所有 $1 \le i \le n$，有 $1 \le b_i \le m$；
• 对所有整数对 $1 \le l \le r \le n$，数组 $b$ 在区间 $[l; r]$ 上的最左最大值位置等于数组 $a$ 在区间 $[l; r]$ 上的最左最大值位置。

由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n,m \le 2 \cdot 10^5$, $n \cdot m \le 10^6$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le m$) — the array $a$.

It is guaranteed that the sum of $n \cdot m$ over all test cases doesn't exceed $10^6$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case print one integer — the number of arrays $b$ that satisfy the conditions from the statement, modulo $10^9+7$.

对于每个测试用例，输出一个整数——满足题目条件的数组 $b$ 的个数，对 $10^9+7$ 取模。

In the first test case, the following $8$ arrays satisfy the conditions from the statement:

• $[1,2,1]$;
• $[1,2,2]$;
• $[1,3,1]$;
• $[1,3,2]$;
• $[1,3,3]$;
• $[2,3,1]$;
• $[2,3,2]$;
• $[2,3,3]$.

In the second test case, the following $5$ arrays satisfy the conditions from the statement:

• $[1,1,1,1]$;
• $[2,1,1,1]$;
• $[2,2,1,1]$;
• $[2,2,2,1]$;
• $[2,2,2,2]$.

在第一个测试用例中，以下 $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]$。