Забрасывать под шкаф!
Они черствеют от тоски,
В такую глушь попав.
Даже секретным агентам порой приходится заниматься самыми обыкновенными вещами.
Однажды, ранним воскресным утром, Гарри Харт решил навести порядок в старинном особняке агенства Кингсман. Спустившись в подвал, он начал подметать пол и случайно обнаружил под шкафом большой чемодан, принадлежавший одному из его предшественников. Как известно, изначально люди из Кингсман были портными, поэтому в чемодане оказались n аккуратно разложенных пар носков. У каждого носка был свой цвет, и у носков в паре был один и тот же цвет и номер пары, которому он принадлежит. Пары пронумерованы различными целыми числами от 1 до n. Кроме того, на каждом носке была маркировка _«Л»_ или _«П»_, обозначающая для левой или правой ноги предназначен этот носок. В каждой паре ровно один носок для левой ноги и ровно один для правой.
Предприимчивый Гарри быстро понял, что носки с такой богатой историей будут отличным подарком для новобранцев, поэтому он решил постирать эти носки и отнести на рынок. Для того, чтобы носки наверняка отстирались, он сложил все носки в одну большую кучу и положил в стиральную машину. По окончании стирки носки выглядели изумительно, но вот беда — все носки оказались перемешаны. Гарри — человек ленивый, поэтому он решил как-то разбить носки на пары так, чтобы в каждой паре был один левый и один правый носок. Конечно, в результате этого носки в одной паре могли оказаться разных цветов. Гарри знает, что среди молодёжи сейчас популярно носить разных цветов на левой и на правой ногах, поэтому Гарри решил презентовать подарок, как «пара разноцветных носков». Однако, в результате перемешивания могла образоваться и пара с двумя носками одинаковых цветов, а в таком случае Гарри обидит кого-нибудь, чего он никак не может допустить.
Гарри решил оценить вероятность того, что он никого не обидит. Для этого ему необходимо знать, сколько есть способов разбить носки на пары так, чтобы в каждой паре был один носок для левой ноги и один носок для правой ноги, а также не было пар, в которых оба носка одного цвета. Два разбиения на пары считаются различными, если различаются множества пар, содержащиеся в них. Две пары носков называются различными, если номера пар, из которых взяты левые носки в этих парах, различаются или номера пар, из которых взяты правые носки, различаются. Обратитесь к примерам для лучшего понимания условия. Так как число таких способов может быть очень большим, Гарри интересует остаток от деления количества способов на 109 + 7.
Помогите Гарри, и он не останется в долгу.
В первой строке задано целое число n — количество пар носков (1 ≤ n ≤ 3 000).
Во второй строке задано n целых чисел a1, a2, ..., an, где ai обозначает цвет носков в паре i (1 ≤ ai ≤ n). Одинаковые цвета обозначены одинаковыми числами, разные — разными.
Выведите одно целое число — остаток от деления числа способов на 109 + 7.
В первом тестовом примере два способа разбить носки на пары выглядят так (первое число в скобках — номер пары, из которой взят левый носок, второе — правый):
Во втором тестовом примере четыре способа разбить носки на пары:
В третьем тестовом примере при любом разбиении будет пара, в которой оба носка будут иметь цвет 2, поэтому ответ — 0.
В четвёртом тестовом примере четыре разбиения выглядят так:
## Входные Данные
В первой строке задано целое число n — количество пар носков (1 ≤ n ≤ 3 000).Во второй строке задано n целых чисел a1, a2, ..., an, где ai обозначает цвет носков в паре i (1 ≤ ai ≤ n). Одинаковые цвета обозначены одинаковыми числами, разные — разными.
## Выходные Данные
Выведите одно целое число — остаток от деления числа способов на 109 + 7.
## Примеры
Входные данные31 2 3Выходные данные2Входные данные41 1 2 2Выходные данные4Входные данные31 2 2Выходные данные0Входные данные41 2 2 3Выходные данные4
## Примечание
В первом тестовом примере два способа разбить носки на пары выглядят так (первое число в скобках — номер пары, из которой взят левый носок, второе — правый): {(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)}.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of sock pairs.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \{1, 2, \dots, n\} $ denotes the color of the socks in pair $ i $.
There are $ n $ left socks and $ n $ right socks. For each pair $ i $, one sock is labeled "Л" (left) and one "П" (right), both of color $ a_i $.
**Constraints**
1. $ 1 \leq n \leq 3000 $
2. $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of bijections $ \sigma: \{1, \dots, n\} \to \{1, \dots, n\} $ such that:
- Each left sock from pair $ i $ is paired with the right sock from pair $ \sigma(i) $.
- For all $ i $, $ a_i \neq a_{\sigma(i)} $ (no monochromatic pair).
The answer is the number of such permutations $ \sigma \in S_n $ satisfying $ a_i \neq a_{\sigma(i)} $ for all $ i $, modulo $ 10^9 + 7 $.
**Formal Objective**
Compute:
$$
\left| \left\{ \sigma \in S_n \mid \forall i \in \{1,\dots,n\},\ a_i \neq a_{\sigma(i)} \right\} \right| \mod (10^9 + 7)
$$