Codeforces Round 833 (Div. 2) |
---|
Finished |
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:
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$$$.
43 31 3 24 22 2 2 26 96 9 6 9 6 99 10010 40 20 20 100 60 80 60 60
8 5 11880 351025663
In the first test case, the following $$$8$$$ arrays satisfy the conditions from the statement:
In the second test case, the following $$$5$$$ arrays satisfy the conditions from the statement:
Name |
---|