27084번 - 카드 뽑기

문제

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

힌트