Description:
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$$$.
Input Format:
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$$$.
Output Format:
For each test case print one integer — the number of arrays $$$b$$$ that satisfy the conditions from the statement, modulo $$$10^9+7$$$.
Note:
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]$$$.