Позиция первого максимума на отрезке \([l; r]\) массива \(x = [x_1, x_2, \ldots, x_n]\) это наименьшее целое число \(i\), такое что \(l \le i \le r\) и \(x_i = \max(x_l, x_{l+1}, \ldots, x_r)\).
Вам дан массив \(a = [a_1, a_2, \ldots, a_n]\) длины \(n\). Найдите количество массивов \(b = [b_1, b_2, \ldots, b_n]\) длины \(n\), удовлетворяющих следующим требованиям:
- \(1 \le b_i \le m\) для всех \(1 \le i \le n\);
- для всех пар \(1 \le l \le r \le n\), позиция первого максимума на отрезке \([l; r]\) массива \(b\) равна позиции первого максимума на отрезке \([l; r]\) массива \(a\).
Так как это количество может быть очень большим, выведите его по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите одно число: количество массивов \(b\), удовлетворяющих требованиям выше, по модулю \(10^9+7\).
Примечание
В первом наборе входных данных следующие \(8\) массивов удовлетворяют требованиям из условия:
- \([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\) массивов удовлетворяют требованиям из условия:
- \([1,1,1,1]\);
- \([2,1,1,1]\);
- \([2,2,1,1]\);
- \([2,2,2,1]\);
- \([2,2,2,2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 3
1 3 2
4 2
2 2 2 2
6 9
6 9 6 9 6 9
9 100
10 40 20 20 100 60 80 60 60
|
8
5
11880
351025663
|