Codeforces Round 833 (Div. 2) |
---|
Закончено |
Позиция первого максимума на отрезке $$$[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$$$, удовлетворяющих следующим требованиям:
Так как это количество может быть очень большим, выведите его по модулю $$$10^9+7$$$.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следуют описания этих наборов.
В первой строке даны два числа $$$n$$$ и $$$m$$$ ($$$2 \le n,m \le 2 \cdot 10^5$$$, $$$n \cdot m \le 10^6$$$).
Во второй строке даны $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$) — массив $$$a$$$.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одно число: количество массивов $$$b$$$, удовлетворяющих требованиям выше, по модулю $$$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
В первом наборе входных данных следующие $$$8$$$ массивов удовлетворяют требованиям из условия:
Во втором наборе входных данных следующие $$$5$$$ массивов удовлетворяют требованиям из условия:
Название |
---|