카드 뽑기

리프는 카드 뽑기 놀이를 하고 있다. $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)$