Сума різноманітностей
Послідовність цілих чисел будемо називати майже монотонною, якщо до деякого числа вона зростає, після чого вона спадає. Тобто, для деякого 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.