CF1748E Yet Another Array Counting Problem
题目描述
对于长度为 $n$ 的序列 $x$，定义其在子段 $[l;r]$ 的“最左端最大值位置”为最小的满足 $l\leq i\leq r$ 且 $x_i=\max_{j=l}^rx_j$ 的整数 $i$。
给定整数 $n,m$ 和长度为 $n$ 的序列 $a$，你需要求出满足下列要求的序列 $b$ 的数量：
- 序列 $b$ 长度为 $n$，且对任意整数 $i(1\leq i\leq n)$ 都有 $1\leq b_i\leq m$ 成立。
- 对任意整数 $l,r(1\leq l\leq r\leq n)$，总有 $a,b$ 在子段 $[l;r]$ 的“最左端最大值位置”相同。
答案对 $10^9+7$ 取模。
每个测试点包含多组数据。
输入格式
第一行输入一个整数 $t(1\leq t\leq10^3)$ 表示数据组数，接下来对于每组数据：
第一行输入两个整数 $n,m(2\leq n,m\leq2\times10^5;\sum n\times m\leq10^6)$。
接下来输入一行 $n$ 个整数表示序列 $a(1\leq a_i\leq m)$。
输出格式
对于每组数据：
输出满足要求的序列 $b$ 的数量对 $10^9+7$ 取模后的值。
### 样例解释
- 对于第一组数据：
- 下面是所有 $8$ 个满足要求的序列 $b$：
$[1,2,1],[1,2,2],[1,3,1],[1,3,2],[1,3,3],[2,3,1],[2,3,2],[2,3,3]$。
- 对于第二组数据：
- 下面是所有 $5$ 个满足要求的序列 $b$：
$[1,1,1,1],[2,1,1,1],[2,2,1,1],[2,2,2,1],[2,2,2,2]$。
说明/提示
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] $ .