Назовем
подпоследовательностью
массива \(a\) непустой массив \(b\) такой, что он может быть получен из массива \(a\) удалением нескольких (возможно, никаких) элементов массива \(a\). Например, массив \([1, 3]\) является попоследовательностью массива \([1, 2, 3]\), но \([3, 1]\) не является.
Назовем
подотрезком
массива \(a\) непустой массив \(b\) такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива \(a\). Например, \([1, 2]\) является подотрезком массива \([1, 2, 3]\), а \([1, 3]\) не является. Несложно заметить, что у массива длины \(n\) ровно \(\frac{n(n + 1)}{2}\) подотрезков.
Назовем массив \(a\) длины \(n\)
возрастающим
, если для любого \(1 \leq i < n\) выполняется \(a_i < a_{i + 1}\).
Монотонностью
массива назовем количество его возрастающих подотрезков.
Дан массив \(a\) длины \(n\). Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).
Примечание
В первом тестовом примере у массива есть \(7\) подпоследовательностей:
-
У массива \([1]\) есть ровно один подотрезок и он является возрастающим.
-
У массива \([2]\) есть ровно один подотрезок и он является возрастающим.
-
У массива \([3]\) есть ровно один подотрезок и он является возрастающим.
-
У массива \([1, 2]\) есть три подотрезка (\([1], [2], [1, 2]\)) и все они являются возрастающими.
-
У массива \([1, 3]\) есть три подотрезка (\([1], [3], [1, 3]\)) и все они являются возрастающими.
-
У массива \([3, 2]\) есть три подотрезка (\([3], [2], [3, 2]\)), но только два из них (\([3]\) и \([2]\)) являются возрастающими.
-
У массива \([1, 3, 2]\) есть шесть подотрезков (\([1], [3], [2], [1, 3], [3, 2], [1, 3, 2]\)) и четыре из них (\([1], [3], [2], [1, 3]\)) являются возрастающими.
Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину \(1\).
