Послідовність цілих чисел будемо називати \textbf{майже монотонною}, якщо до деякого числа вона зростає, після чого вона спадає. Тобто, для деякого \textbf{1} ≤ \textbf{k} ≤ \textbf{n} виконується: \textbf{a_1} ≤ \textbf{a_2} ≤ ... ≤ \textbf{a_k}, \textbf{a_k} ≥ \textbf{a_\{k+1\}} ≥ ... ≥ \textbf{a_n}. \textbf{Різноманітність} послідовності \textbf{a_1, a_2, ..., a_n }будемо визначати, як кількість можливих послідовностей цілих чисел \textbf{b_1, b_2, ..., b_n}, для яких \textbf{0} ≤ \textbf{b_i} < \textbf{a_i} і всі числа \textbf{b_1, b_2, ..., b_n} -- різні. Ваша задача, знайти суму різноманітностей всіх різних майже монотонних підпослідовностей заданої послідовності за модулем \textbf{1 000 000 007}. Підпослідовністю будемо називати будь-яку послідовність чисел, отриману видаленням деякої кількості чисел (можливо нульову) з заданої послідовності. Порожню послідовність будемо вважати підпослідовністю будь-якої. Дві послідовності різні, якщо існує позиція в якій числа в послідовністях відрізняються одне від одного. \InputFile У першому рядку знаходиться число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}) -- кількість елементів вхідної послідовності. У другому рядку записана послідовність цілих чисел \textbf{c_i} (\textbf{1} ≤ \textbf{c_i} ≤ \textbf{100}) -- елементи заданої послідовності. \OutputFile В єдиному рядку повинно міститись знайдене число за модулем \textbf{1 000 000 007}.