The sum of diversities
A sequence of integers is termed almost monotonic if it first increases to a certain point and then decreases. Specifically, for some 1 ≤ k ≤ n, the following conditions are satisfied:
a_1 ≤ a_2 ≤ ... ≤ a_k, a_k ≥ a_{k+1} ≥ ... ≥ a_n.
The diversity of the sequence a_1, a_2, ..., a_n is defined as the number of possible sequences of integers b_1, b_2, ..., b_n, where 0 ≤ b_i < a_i and all numbers b_1, b_2, ..., b_n are distinct.
Your task is to calculate the sum of the diversities of all distinct almost monotonic subsequences of the given sequence, and provide the result modulo 1 000 000 007. A subsequence is any sequence derived by removing some elements (possibly none) from the original sequence. An empty sequence is considered a subsequence of any sequence. Two sequences are considered different if they differ at any position.
Input
The first line contains the integer N (1 ≤ N ≤ 100) – the number of elements in the input sequence. The second line contains the sequence of integers c_i (1 ≤ c_i ≤ 100) – the elements of the given sequence.
Output
Output a single line with the computed number modulo 1 000 000 007.