## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Yet Another Array Counting Problem Codeforces Solution

E. Yet Another Array Counting Problem
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The position of the leftmost maximum on the segment $\left[l;r\right]$ of array $x=\left[{x}_{1},{x}_{2},\dots ,{x}_{n}\right]$ is the smallest integer $i$ such that $l\le i\le r$ and ${x}_{i}=max\left({x}_{l},{x}_{l+1},\dots ,{x}_{r}\right)$.

You are given an array $a=\left[{a}_{1},{a}_{2},\dots ,{a}_{n}\right]$ of length $n$. Find the number of integer arrays $b=\left[{b}_{1},{b}_{2},\dots ,{b}_{n}\right]$ 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 $\left[l;r\right]$ of the array $b$ is equal to the position of the leftmost maximum on the segment $\left[l;r\right]$ 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},\dots ,{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$.

Note

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

• $\left[1,2,1\right]$;
• $\left[1,2,2\right]$;
• $\left[1,3,1\right]$;
• $\left[1,3,2\right]$;
• $\left[1,3,3\right]$;
• $\left[2,3,1\right]$;
• $\left[2,3,2\right]$;
• $\left[2,3,3\right]$.

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

• $\left[1,1,1,1\right]$;
• $\left[2,1,1,1\right]$;
• $\left[2,2,1,1\right]$;
• $\left[2,2,2,1\right]$;
• $\left[2,2,2,2\right]$