# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Maruo and the Sequence

Maruo has a sequece A = **{a _{1},a_{2},……a_{n}}**.

Let us define a function

**func(A,l,r)**which is the minimum

**i**such that

**a**is the maximum value where

_{i}**l<=i<=r**.

Two sequences

**A**and

**B**are similar if they have the same length

**n**and for every

**1<=l<=r<=n**,

**func(A,l,r)**=

**func(B,l,r)**.

For any given sequence A=

**{a**, we define the weight of a sequence B=

_{1},a_{2},……a_{n}}**{b**be

_{1},b_{2},……b_{n}}**∑b**, where

_{i}**1<=i<=n**, if the two sequences

**A**and

**B**are similar. Otherwise, we let the weight be equal to

**0**. If each element of

**B**is chosen independently and uniform randomly between 0 and 1, find the expected weight of

**B**.

Please note that the elements of **B** are real numbers between **0** and **1** inclusive, and not necessarily only **0** or **1**.

### Input

The first line will contain **n** (the length of the sequence) **1<=n<=1000000**.

The second line contains **n** integers (1<=a_{i}<=n) denoting the sequence.

### Output

The expected weight will be a rational number **p/q**, where p and q are co-prime numbers.

Output the answer modulo 10^{9}+7 i.e. output **pq ^{-1}** modulo 10

^{9}+7.

### Samples

Input | Output |
---|---|

3 1 2 3 | 250000002 |

#### sazerterus25

→

Login to submit