Гарри и носки

문제

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

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

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

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

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

Даже секретным агентам порой приходится заниматься самыми обыкновенными вещами.

Однажды, ранним воскресным утром, Гарри Харт решил навести порядок в старинном особняке агенства Кингсман. Спустившись в подвал, он начал подметать пол и случайно обнаружил под шкафом большой чемодан, принадлежавший одному из его предшественников. Как известно, изначально люди из Кингсман были портными, поэтому в чемодане оказались $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)\\}$ .