Сумма разнообразий
Последовательность целых чисел будем называть почти монотонной, если к некоторому числу она возрастает, после чего она убывает. То есть, для некоторого 1 ≤ k ≤ n виполняется:
a_1 ≤ a_2 ≤ ... ≤ a_k, a_k ≥ a_{k+1} ≥ ... ≥ a_n.
Разнообразие последовательности a_1, a_2, ..., a_n определим как количество возможных последовательностей целых чисел b_1, b_2, ..., b_n, для которых 0 ≤ b_i < a_i и все числа b_1, b_2, ..., b_n – разные.
Ваша задача, найти суму разнообразий всех разных почти монотонных подпоследовательностей заданной последовательности по модулю 1 000 000 007. Подпоследовательностью будем называть любую последовательность чисел, полученную удалением некоторого количества чисел (возможно нулевое) из заданной последовательеости. Пустую последовательность будем считать подпоследовательностью любой. Две последовательности разные, если существует позиция в которой числа в последовательностях отличаются одно от другого.
Входные данные
В первой строке находится число N (1 ≤ N ≤ 100) – количество элементов входной последовательности. Во второй строке записана последовательность целых чисел c_i (1 ≤ c_i ≤ 100) – элементы заданной последовательности.
Выходные данные
В единственной строке должно находится найденное число по модулю 1 000 000 007.