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

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

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

见题面 Input 部分

见题面 Output 部分

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