A15553. 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$ .

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$ .

For each test case print one integer — the number of arrays $b$ that satisfy the conditions from the statement, modulo $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]$ .