406414: GYM102397 H Mahmoud and the flagstones

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.

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.

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

5
3 5 5 1 2

6

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.