e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

I Cup Alexandria 2010

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

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

a1a2 ≤ ... ≤ ak, akak+1 ≥ ... ≥ an.

Разнообразие последовательности a1, a2, ..., anопределим как количество возможных последовательностей целых чисел b1, b2, ..., bn, для которых 0bi < ai и все числа b1, b2, ..., bn – разные.

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

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
3
2 3 1

Output example #1
15

Example description: Разнообразие (пустая последовательность) = 1 Разнообразие (2) = 2 Разнообразие (3) = 3 Разнообразие (2 3) = 4 Разнообразие (1) = 1 Разнообразие (2 1) = 1 Разнообразие (3 1) = 2 Разнообразие (2 3 1) = 1 Всего: 15