H. Mahmoud and the flagstones
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

When Mahmoud was walking in BetaCity, he saw a sequence of $$$n$$$ flagstones each one of them has a color $$$a_i$$$.

Mahmoud hates different things, so he asked Ayoub to count the number of ways to choose a nonempty subsets of flagstones such that the color of all flagstones in the subset is the same.

Ayoub is very lazy, and he notice that the number of subsets is very large, so he needs your help.

print the number of nonempty subsets of flagstone that have the same color.

As this number may be too large, print it modulo $$$10^{9}$$$ + 7.

Input

First line of input contains integer $$$n$$$ $$$(1 \leq n \leq 10^5 )$$$, the length of the sequence.

The second line contains $$$n$$$ integers $$$ a_1 , a_2 , ... , a_n $$$ $$$(1 \leq a_i \leq 100000)$$$, each of them denotes the color of the $$$i^{th}$$$ flagstone.

Output

print the number of nonempty subsets of flagstone that have the same color modulo $$$10^{9}$$$ + 7.

Example
Input
5
3 5 5 1 2
Output
6
Note

in the example, the subsets are:

{$$$a_1$$$} —> {$$$3$$$}

{$$$a_2$$$} —> {$$$5$$$}

{$$$a_3$$$} —> {$$$5$$$}

{$$$a_4$$$} —> {$$$1$$$}

{$$$a_5$$$} —> {$$$2$$$}

{$$$a_2,a_3$$$} —> {$$$5,5$$$}

any other subset will have different colors.