Сума різноманітностей#1349
Послідовність цілих чисел називається майже монотонною, якщо вона спочатку не спадає (можливо, залишаючись сталою) до певної позиції, а потім не зростає (можливо, також залишаючись сталою). Тобто, для деякого 1 \leq k \leq n,
Різноманітність послідовності a_1, a_2, \ldots, a_n визначається як кількість послідовностей цілих чисел b_1, b_2, \ldots, b_n, для яких 0 \leq b_i < a_i і всі b_1, b_2, \ldots, b_n різні.
Ваша задача — знайти суму різноманітностей усіх різних майже монотонних підпослідовностей заданої послідовності за модулем 1 000 000 007.
Підпослідовність — це будь-яка послідовність, яку можна отримати з оригінальної шляхом видалення деяких елементів (можливо, жодного). Порожня послідовність також вважається підпослідовністю будь-якої. Дві послідовності різні, якщо існує позиція, у якій їх відповідні елементи відрізняються.
Перший рядок містить ціле число (1 \leq N \leq 100) — кількість елементів у послідовності. Другий рядок містить цілі числа c_i (1 \leq c_i \leq 100) — елементи послідовності.
Виведіть одне число — відповідь за модулем 1 000 000 007.
Приклад 1