E. MARI
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
So... do you need me to help you in anything? All it costs is your love
— Mari, Dreamspace

Mari is currently baking cookies for OMORI's quest (as they need a lot of juice and heart in this one). She currently has a cookie dough with nutrition value $$$a_1$$$.

There are $$$n-1$$$ ovens numbered from $$$1$$$ to $$$n-1$$$. Mari puts each cookie in every oven by order, starting from oven $$$1$$$ till oven $$$n-1$$$. Ovens in dreams are different from casual ovens; they have two modes: Heating mode and Freezing mode, and also each oven $$$i$$$ has a power value $$$a_{i+1}$$$.

When baking a cookie with nutrition $$$x$$$ in the $$$i$$$-th oven, Mari can do one of the following options :

  1. Set the $$$i$$$-th oven on heating mode; this will change the nutrition value of the cookie from $$$x$$$ to $$$\max(x,a_{i+1})$$$.
  2. Set the $$$i$$$-th oven on freezing mode; this will change the nutrition value of the cookie from $$$x$$$ to $$$\min(x,a_{i+1})$$$.

Mari will try every possible configuration of modes to all $$$n-1$$$ ovens, and she wants to find the summation of the nutrition values of all final cookies over every possible configuration of ovens. Since this sum can be large, Mari wants its value taken under modulo $$$10^9+7$$$.

Two configurations of ovens are considered different if there exists an oven $$$j$$$ $$$(1 \le j \lt n)$$$ such that oven $$$j$$$ is set on heating mode in one configuration and set on freezing mode in the other one.

Input

The first line of input contains one integer $$$n$$$ $$$(1 \le n \le 2\times 10^5)$$$ — the number of ovens $$$+ 1$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^9)$$$ separated by spaces — the initial nutrition value of the cookie dough and the power values of each oven.

Output

Output one line containing the summation of all final cookies' nutrition values, taken under modulo $$$10^9 + 7$$$.

Examples
Input
3
1 2 1
Output
5
Input
5
2 2 2 2 2
Output
32
Note

In the first example, there are $$$4$$$ possibilities:

  1. Mari sets both ovens on heating mode; the final nutrition value of the cookie will be $$$\max(\max(1, 2), 1) = 2$$$.
  2. Mari sets both ovens on freezing mode; the final nutrition value of the cookie will be $$$\min(\min(1, 2), 1) = 1$$$.
  3. Mari sets the first oven on heating mode and the second one on freezing mode; the final nutrition value of the cookie will be $$$\min(\max(1, 2), 1) = 1$$$.
  4. Mari sets the first oven on freezing mode and the second one on heating mode; the final nutrition value of the cookie will be $$$\max(\min(1, 2), 1) = 1$$$.

So the summation of all final nutrition values will be : $$$2+1+1+1 = 5$$$.

A poster showing Mari's pieces of advice about baking cookies