King of Buckets is very nervous lately. His treasure keepers have found a new way to keep track of how much gold he has that does not allow any eavesdropper to know the exact size of the treasure. Now all he can see every month is a number which he doesn't know how to interpret. What if they are secretly stealing his gold!?

The treasure looks like this: there are ** N** boxes, each of them labeled with an integer

`, depending on the contents of the box. They have been arranged over time in a straight line, in the order in which the king had received them from admirers. To compute the value of the treasure, the treasure keepers take each`

**L****subsequence of boxes and assign it to a bucket. Different subsequences will be assigned to the same bucket if they contain the same labels, regardless of the order. The value of the treasure is computed as**

`non-empty`**, where**

`SUM(|bucket(i)|`^{2})**represents the number of subsequences assigned to the**

`|bucket(i)|`**bucket, for**

`i`^{th}**.**

`1 ≤ i ≤ the number of resulting buckets` For instance, if the treasure is formed from ** 1, 2, 2, 3, 1** (

*i.e.*

**box with label**

`one`**,**

`1`**consecutive boxes with label**

`two`**and so on) then**

`2`**,**

`{1, 2, 3}``,`

**{1, 2, 3}****and**

`{2, 3, 1}``are all part of the same bucket, whereas`

**{2, 3, 1}****is alone in its bucket. Note that**

`{3}`**and**

`{1, 2, 3}`**are different subsequences because in the first case**

`{1, 2, 3}`**is taken from the**

`2`**position in the string, whereas in the second case it is taken from the**

`2`^{nd}**position.**

`3`^{rd}** Note:** A subsequence of an array

**is an array**

`S = s`_{1}, s_{2}, …, s_{n}**such that**

`S' = s`_{i1}, s_{i2}, …, s_{ik}**, and**

`1 ≤ i`_{1}< i_{2}< … < i_{k}≤ n**.**

`k ≥ 1`### Input

On the first line there will be the number ** N** of boxes in the treasure, followed on the next line by

**integer numbers representing the labels.**

`N`### Output

The value ** S** of the treasure, as computed by the treasure keepers.

**As this number can be very large, please print the number modulo**

`10`^{9}+ 7### Restrictions

`1 ≤ N ≤ 10`^{5}`1 ≤ L ≤ 10`^{6}

### Sample

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

31 2 2 | 11 | The subsequences of labels are: {1}, {2}, {2}, {1, 2}, {1, 2}, {2, 2} and {1, 2, 2}. The following buckets are created: SUM(|buckets(i)| |

51 2 2 3 1 | 71 | This one is a bit tricky. |

Because two subsequences will be in the same bucket if they have the same elements, their position does not really matter.

Let's fix a some arbitrary frequencies for all the elements in our initial array.

Let this array be `a`` a[i]= the arbitrary frequency of the number i `

Let's also denote:` freq[i] = the total frequency of the number i in the whole array `**Note that a[i] ≤ freq[i] for each i**

The size of the bucket containing all these subsequences with be:

Now we only need a way to compute the sum of products of all possible ** a**. We can compute the product of a sum which will give us every single possbile combination. This product is the following:

In the end, because we want the size of each bucket to be squared, and remove the empty set, we need to compute the following formula: