| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 10 | 5 | 5 | 50.000% |
Не надо грязные носки
Забрасывать под шкаф!
Они черствеют от тоски,
В такую глушь попав.
Юнна Мориц, Стирать свои носки!
Даже секретным агентам порой приходится заниматься самыми обыкновенными вещами.
Однажды, ранним воскресным утром, Гарри Харт решил навести порядок в старинном особняке агенства Кингсман. Спустившись в подвал, он начал подметать пол и случайно обнаружил под шкафом большой чемодан, принадлежавший одному из его предшественников. Как известно, изначально люди из Кингсман были портными, поэтому в чемодане оказались $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$.
3 1 2 3
2
4 1 1 2 2
4
3 1 2 2
0
4 1 2 2 3
4
В первом тестовом примере два способа разбить носки на пары выглядят так (первое число в скобках --- номер пары, из которой взят левый носок, второе --- правый):
Во втором тестовом примере четыре способа разбить носки на пары:
В третьем тестовом примере при любом разбиении будет пара, в которой оба носка будут иметь цвет 2ドル,ドル поэтому ответ --- 0ドル$.
В четвёртом тестовом примере четыре разбиения выглядят так: