해리와 양말

Не надо грязные носки

Забрасывать под шкаф!

Они черствеют от тоски,

В такую глушь попав.

---

Юнна Мориц, Стирать свои носки!

때로는 비밀 요원도 아주 평범한 일을 해야 한다.

어느 일요일 이른 아침, 해리 하트는 킹스맨 저택의 지하실을 청소하다가 옷장 아래에서 큰 가방을 발견했다. 킹스맨은 원래 재단사 집단이었으므로, 가방 안에는 $n$쌍의 양말이 가지런히 개어 있었다. 양말마다 색이 정해져 있고, 같은 쌍의 두 양말은 색과 쌍 번호가 같다. 쌍 번호는 1부터 $n$까지의 서로 다른 정수이다. 각 양말에는 왼발용을 뜻하는 <<Л>> 또는 오른발용을 뜻하는 <<П>> 표시가 있다. 각 쌍에는 왼발용 양말이 정확히 하나, 오른발용 양말이 정확히 하나 있다.

해리는 양말을 세탁기에 한꺼번에 넣었다. 세탁이 끝나자 양말은 깨끗해졌지만 모두 뒤섞여 있었다. 해리는 게으른 편이라, 각 짝이 왼발용 양말 하나와 오른발용 양말 하나로 이루어지도록 양말을 다시 짝짓기로 했다. 짝지은 두 양말의 색은 달라도 된다. 요즘 젊은이들은 왼발과 오른발에 서로 다른 색 양말을 신는 것을 좋아하므로, 해리는 색이 다른 양말 짝을 선물로 내놓을 생각이다. 그러나 뒤섞인 결과 색이 같은 두 양말이 한 짝이 될 수도 있고, 그러면 누군가 기분이 상하게 되므로 해리는 이를 허용할 수 없다.

해리는 아무도 기분 상하지 않을 확률을 가늠하고 싶어 한다. 이를 위해 각 짝이 왼발용 양말 하나와 오른발용 양말 하나로 이루어지고, 색이 같은 두 양말로 이루어진 짝이 없는 짝짓기 방법의 수를 알아야 한다. 두 짝짓기는 포함된 짝의 집합이 다를 때 서로 다른 것으로 본다. 두 짝은 왼발 양말이 온 쌍 번호나 오른발 양말이 온 쌍 번호가 다르면 서로 다른 것이다. 예제를 보면 이해하기 쉽다. 방법의 수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구하라.

해리를 도와주면 그는 반드시 보답할 것이다.

첫째 줄에 양말 쌍의 개수 $n$이 주어진다 ($1 \le n \le 3\,000$).

둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. 여기서 $a_i$는 $i$번째 쌍 양말의 색이다 ($1 \le a_i \le n$). 같은 색은 같은 수로, 다른 색은 다른 수로 표시된다.

짝짓기 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 번째 테스트에서 짝짓기 방법은 두 가지이다. 괄호 안의 첫 번째 수는 왼발 양말이 온 쌍 번호, 두 번째 수는 오른발 양말이 온 쌍 번호이다.

• $\{(1, 2), (2, 3), (3, 1)\}$
• $\{(1, 3), (2, 1), (3, 2)\}$

두 번째 테스트에서 짝짓기 방법은 네 가지이다.

• $\{(1, 3), (2, 4), (3, 1), (4, 2)\}$
• $\{(1, 4), (2, 3), (3, 1), (4, 2)\}$
• $\{(1, 3), (2, 4), (3, 2), (4, 1)\}$
• $\{(1, 4), (2, 3), (3, 2), (4, 1)\}$

세 번째 테스트에서는 어떤 짝짓기를 해도 색이 $2$인 양말 두 장이 한 짝이 되므로 답은 $0$이다.

네 번째 테스트에서 짝짓기 방법은 네 가지이다.

• $\{(1, 2), (2, 1), (3, 4), (4, 3)\}$
• $\{(1, 3), (2, 1), (3, 4), (4, 2)\}$
• $\{(1, 2), (2, 4), (3, 1), (4, 3)\}$
• $\{(1, 3), (2, 4), (3, 1), (4, 2)\}$