G. Взвешенные возрастающие подпоследовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$.

Последовательность индексов $$$i_1 < i_2 < \ldots < i_k$$$ длины $$$k$$$ задаёт подпоследовательность $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ длины $$$k$$$ последовательности $$$a$$$.

Подпоследовательность $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ длины $$$k$$$ последовательности $$$a$$$ называется возрастающей, если $$$a_{i_j} < a_{i_{j+1}}$$$ для всех $$$1 \leq j < k$$$.

Назовём весом возрастающей подпоследовательности $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ длины $$$k$$$ последовательности $$$a$$$ количество таких $$$1 \leq j \leq k$$$, для которых существует $$$i_k < x \leq n$$$, такой что $$$a_x > a_{i_j}$$$.

Например, если $$$a = [6, 4, 8, 6, 5]$$$, то последовательность индексов $$$i = [2, 4]$$$ задаёт возрастающую подпоследовательность $$$[4, 6]$$$ последовательности $$$a$$$. Вес этой возрастающей подпоследовательности будет равен $$$1$$$, так как для $$$j = 1$$$ существует $$$x = 5$$$ для которого $$$a_5 = 5 > a_{i_1} = 4$$$, а для $$$j = 2$$$ такого $$$x$$$ не существует.

Найдите сумму весов всех возрастающих подпоследовательностей $$$a$$$ по модулю $$$10^9+7$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано одно число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина последовательности $$$a$$$.

Во второй строке дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — последовательность $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число: сумму весов всех возрастающих подпоследовательностей $$$a$$$ по модулю $$$10^9+7$$$.

Пример
Входные данные
4
5
6 4 8 6 5
4
1 2 3 4
3
3 2 2
4
4 5 6 5
Выходные данные
4
12
0
6
Примечание

В первом наборе входных данных следующие возрастающие подпоследовательности $$$a$$$ имеют ненулевой вес:

  • $$$[a_1] = [6]$$$ имеет вес $$$1$$$.
  • $$$[a_2] = [4]$$$ имеет вес $$$1$$$.
  • $$$[a_2, a_3] = [4, 8]$$$ имеет вес $$$1$$$.
  • $$$[a_2, a_4] = [4, 6]$$$ имеет вес $$$1$$$.
Сумма весов всех возрастающих подпоследовательностей равна $$$4$$$.

Во втором тестовом случае существует $$$7$$$ возрастающих подпоследовательностей $$$a$$$ ненулевого веса: $$$3$$$ веса $$$1$$$, $$$3$$$ веса $$$2$$$ и $$$1$$$ веса $$$3$$$. Сумма весов равна $$$12$$$.