카드 뽑기

리프는 카드 뽑기 놀이를 하고 있다. $N$장의 카드가 일렬로 나열되어 있고, 각각의 카드에는 양의 정수 1개가 적혀있다. 카드 뽑기 놀이는 다음과 같은 과정으로 진행된다.

• 1번째 카드부터 $N$번째 카드까지 차례로 보면서 뽑을지 말지 결정한다. 각 카드를 뽑는 시행은 독립적이다.
• 뽑은 카드가 없을 경우 뽑기를 다시 진행한다.
• 뽑은 카드에 적힌 정수들이 모두 다를 경우 게임에서 승리한다.

리프가 각 카드를 뽑을 확률이 정확히 $\frac{1}{2}$라고 할 때, 게임에서 승리할 확률 $p$를 구하여라.

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 $N$개의 정수 $A\_1, A\_2, \ldots, A\_N$이 주어진다. $i$번째 카드에 적힌 정수는 $A\_i$이다.

첫 번째 줄에 $(2^N-1)p$를 $10^9+7$로 나눈 나머지를 출력한다. $(2^N-1)p$가 항상 정수임을 증명할 수 있다.

• $1 \le N \le 2 \times 10^5$
• $1 \le A\_i \le N$ $(1 \le i \le N)$