[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 [𝑙;𝑟]$[l;r]$ of array 𝑥=[𝑥1,𝑥2,…,𝑥𝑛]$x=[x_1,x_2,\dots ,x_n]$ is the smallest integer 𝑖$i$ such that 𝑙≤𝑖≤𝑟$l\le i\le r$ and 𝑥𝑖=max(𝑥𝑙,𝑥𝑙+1,…,𝑥𝑟)$x_i=max(x_l,x_{l+1},\dots ,x_r)$.

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

• 1≤𝑏𝑖≤𝑚$1\le b_i\le m$ for all 1≤𝑖≤𝑛$1\le i\le n$;
• for all pairs of integers 1≤𝑙≤𝑟≤𝑛$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 109+7${10}^9+7$.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤103$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≤𝑛,𝑚≤2⋅105$2\le n,m\le 2\cdot {10}^5$, 𝑛⋅𝑚≤106$n\cdot m\le {10}^6$).

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑚$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 106${10}^6$.

Output

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

Note

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

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

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

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