Sizə tək ədədi verilir. ədəddən ibarət [a_1, a_2, \ldots, a_n] massivi üçün onun dəyərini n+1 təpəli qrafda mükəmməl uyğunlaşmanın maksimal çəkisi kimi təyin edək; bu qrafda i<j üçün tilinin çəkisi max(a_i, a_{i+1}, \ldots, a_{j-1}) kimi təyin olunur.
Məsələn, [1, 30, 15] massivi üçün biz aralarındakı məsafələri aşağıdakı kimi olan təpəli qraf alırıq:
d(1, 2) = 1
d(1, 3) = d(1, 4) = d(2, 3) = d(2, 4) = 30
d(3, 4) = 15
Burada ((1, 2), (3, 4)) uyğunlaşmasının çəkisi , ((1, 3), (2, 4)) və ((1, 4), (2, 3)) uyğunlaşmalarının çəkisi isə -dır, buna görə də bütün massivin dəyəri -a bərabərdir.
Sizə cüt-cüt fərqli elementlərdən ibarət uzunluğunda massivi verilir. Bu massivin bütün yerdəyişmələrinin dəyərləri cəmini 10^9 + 7 moduluna görə tapın.
Xatırladaq ki, təpəli çəkili qrafda mükəmməl uyğunlaşma — elə tildən ibarət çoxluqdur ki, hər bir təpə dəqiq bir tilin ucudur. Mükəmməl uyğunlaşmanın çəkisi seçilmiş bütün tilin çəkiləri cəmidir.
Birinci sətirdə bir tam ədədi verilir (1 \leq n \leq 99\,999, təkdir) — massivin uzunluğu.
İkinci sətirdə cüt-cüt fərqli tam ədəd b_1, b_2, \ldots, b_n verilir (1 \leq b_i \leq 10^8) — massivin elementləri.
Bu massivin bütün yerdəyişmələrinin dəyərləri cəmini 10^9 + 7 moduluna görə çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunədə:
[1, 30, 15] və [15, 30, 1] massivlərinin dəyərləri -a bərabərdir.
[1, 15, 30], [30, 15, 1], [15, 1, 30], [30, 1, 15] massivlərinin dəyərləri -ə bərabərdir.
Bütün yerdəyişmələr üzrə cəm 60\cdot 2 + 45\cdot 4 = 300-ə bərabərdir.