CF1748E Yet Another Array Counting Problem

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

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

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