Card Drawing

Interview

Time limit1sMemory limit1024 MB

Summary

Given N cards with values, count the nonempty subsets of cards whose values are all distinct, modulo 10^9+7.

Level: Medium4 of 10
Topics: Hash map, Combinatorics
Solved: No attempts yet

Problem

Leaf is playing a card drawing game. There are $N$ cards in a row, and each card has one positive integer written on it. The game proceeds as follows.

Going from the 1st card to the $N$ th card in order, decide whether to draw each card. Each draw is independent.
If no card was drawn, repeat the drawing process.
If all integers on the drawn cards are different, the player wins.

Assuming Leaf draws each card with probability exactly $\frac{1}{2}$ , find the probability $p$ that Leaf wins.

Input

The first line contains $N$ .

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ . The integer on the $i$ -th card is $A_i$ .

Output

Print the remainder of $(2^N-1)p$ divided by $10^9+7$ on the first line. It can be proven that $(2^N-1)p$ is always an integer.

Constraints

$1 \le N \le 2 \times 10^5$
$1 \le A_i \le N$ $(1 \le i \le N)$

Examples1

Example 1
Input
```
4
1 2 3 1
```
Expected output
```
11
```