Вам дана последовательность целых чисел \(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\).
Примечание
В первом наборе входных данных следующие возрастающие подпоследовательности \(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\).