Забрасывать под шкаф!
Они черствеют от тоски,
В такую глушь попав.
Даже секретным агентам порой приходится заниматься самыми обыкновенными вещами.
Однажды, ранним воскресным утром, Гарри Харт решил навести порядок в старинном особняке агенства Кингсман. Спустившись в подвал, он начал подметать пол и случайно обнаружил под шкафом большой чемодан, принадлежавший одному из его предшественников. Как известно, изначально люди из Кингсман были портными, поэтому в чемодане оказались n аккуратно разложенных пар носков. У каждого носка был свой цвет, и у носков в паре был один и тот же цвет и номер пары, которому он принадлежит. Пары пронумерованы различными целыми числами от 1 до n. Кроме того, на каждом носке была маркировка «Л» или «П», обозначающая для левой или правой ноги предназначен этот носок. В каждой паре ровно один носок для левой ноги и ровно один для правой.
Предприимчивый Гарри быстро понял, что носки с такой богатой историей будут отличным подарком для новобранцев, поэтому он решил постирать эти носки и отнести на рынок. Для того, чтобы носки наверняка отстирались, он сложил все носки в одну большую кучу и положил в стиральную машину. По окончании стирки носки выглядели изумительно, но вот беда — все носки оказались перемешаны. Гарри — человек ленивый, поэтому он решил как-то разбить носки на пары так, чтобы в каждой паре был один левый и один правый носок. Конечно, в результате этого носки в одной паре могли оказаться разных цветов. Гарри знает, что среди молодёжи сейчас популярно носить разных цветов на левой и на правой ногах, поэтому Гарри решил презентовать подарок, как «пара разноцветных носков». Однако, в результате перемешивания могла образоваться и пара с двумя носками одинаковых цветов, а в таком случае Гарри обидит кого-нибудь, чего он никак не может допустить.
Гарри решил оценить вероятность того, что он никого не обидит. Для этого ему необходимо знать, сколько есть способов разбить носки на пары так, чтобы в каждой паре был один носок для левой ноги и один носок для правой ноги, а также не было пар, в которых оба носка одного цвета. Два разбиения на пары считаются различными, если различаются множества пар, содержащиеся в них. Две пары носков называются различными, если номера пар, из которых взяты левые носки в этих парах, различаются или номера пар, из которых взяты правые носки, различаются. Обратитесь к примерам для лучшего понимания условия. Так как число таких способов может быть очень большим, Гарри интересует остаток от деления количества способов на 109 + 7.
Помогите Гарри, и он не останется в долгу.
В первой строке задано целое число n — количество пар носков (1 ≤ n ≤ 3 000).
Во второй строке задано n целых чисел a1, a2, ..., an, где ai обозначает цвет носков в паре i (1 ≤ ai ≤ n). Одинаковые цвета обозначены одинаковыми числами, разные — разными.
Выведите одно целое число — остаток от деления числа способов на 109 + 7.
3
1 2 3
2
4
1 1 2 2
4
3
1 2 2
0
4
1 2 2 3
4
В первом тестовом примере два способа разбить носки на пары выглядят так (первое число в скобках — номер пары, из которой взят левый носок, второе — правый):
Во втором тестовом примере четыре способа разбить носки на пары:
В третьем тестовом примере при любом разбиении будет пара, в которой оба носка будут иметь цвет 2, поэтому ответ — 0.
В четвёртом тестовом примере четыре разбиения выглядят так:
