eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумма разнообразий

Сумма разнообразий

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Последовательность целых чисел будем называть почти монотонной, если к некоторому числу она возрастает, после чего она убывает. То есть, для некоторого 1kn виполняется:

a_1a_2 ≤ ... ≤ a_k, a_ka_{k+1} ≥ ... ≥ a_n.

Разнообразие последовательности a_1, a_2, ..., a_n определим как количество возможных последовательностей целых чисел b_1, b_2, ..., b_n, для которых 0b_i < a_i и все числа b_1, b_2, ..., b_n – разные.

Ваша задача, найти суму разнообразий всех разных почти монотонных подпоследовательностей заданной последовательности по модулю 1 000 000 007. Подпоследовательностью будем называть любую последовательность чисел, полученную удалением некоторого количества чисел (возможно нулевое) из заданной последовательеости. Пустую последовательность будем считать подпоследовательностью любой. Две последовательности разные, если существует позиция в которой числа в последовательностях отличаются одно от другого.

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

В первой строке находится число N (1N100) – количество элементов входной последовательности. Во второй строке записана последовательность целых чисел c_i (1c_i100) – элементы заданной последовательности.

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

В единственной строке должно находится найденное число по модулю 1 000 000 007.

Пример

Входные данные #1
3
2 3 1

Выходные данные #1
15