The sum of diversities#1349
A sequence of integers is called almost monotonic if it first increases (possibly remaining constant) to a certain point and then decreases (possibly remaining constant). That is, for some 1 \leq k \leq n,
The diversity of a sequence a_1, a_2, \ldots, a_n is defined as the number of sequences of integers b_1, b_2, \ldots, b_n such that 0 \leq b_i < a_i and all b_1, b_2, \ldots, b_n are distinct.
Your task is to find the sum of the diversities of all distinct almost monotonic subsequences of the given sequence, modulo 1 000 000 007.
A subsequence is any sequence derived from the original by deleting some elements (possibly none). The empty sequence is considered a subsequence of any sequence. Two sequences are different if there is a position at which their corresponding elements differ.
The first line contains the integer (1 \leq N \leq 100) — the number of elements in the sequence. The second line contains the integers c_i (1 \leq c_i \leq 100) — the elements of the sequence.
Output a single number, the answer modulo 1 000 000 007.
Example 1