Medie

Cerință

Se dă un șir $A$ de lungime $N$.
Putem face următoarea operație de câte ori dorim:

• Alegem un $i$, $1 < i < N$, și setăm $A_i$ pe media vecinilor ($A_{i-1}$ și $A_{i+1}$)
  
  Care este suma maximă a șirului care se poate obține?

Date de intrare

Pe prima linie se găsește $N$. Pe următoarea linie se găsește șirul $A$.

Date de ieșire

Suma maximă modulo $10^9+7$.

Restricții și precizări

• $1 \leq N, A_i \leq 10^6$;
• Pentru a scrie rezultatul modulo $10^9+7$ trebuie privit ca o fracție $\frac{p}{q}$ care este echivalentă cu $p \cdot q^{-1}$.
• În eventualitatea în care suma poate sa crească la infinit, se cere să se afișeze primul număr rațional pe care suma nu îl poate atinge.
• Se poate demonstra că un astfel de număr există.

Exemplul 1

stdin

3
3 1 5

stdout

12

Explicație

Alegem $i=2$ și rezultă șirul ${3,4,5}$ de sumă $12$.

Exemplul 2

stdin

3
1 1 2

stdout

500000008

Explicație

Șirul rezultat este ${1,1.5,2}$ de sumă $4.5$ care modulo $10^9+7$ este $500000008$.