{"raw_statement":[{"iden":"statement","content":"Забрасывать под шкаф!\n\nОни черствеют от тоски,\n\nВ такую глушь попав. \n\nДаже секретным агентам порой приходится заниматься самыми обыкновенными вещами.\n\nОднажды, ранним воскресным утром, Гарри Харт решил навести порядок в старинном особняке агенства Кингсман. Спустившись в подвал, он начал подметать пол и случайно обнаружил под шкафом большой чемодан, принадлежавший одному из его предшественников. Как известно, изначально люди из Кингсман были портными, поэтому в чемодане оказались n аккуратно разложенных пар носков. У каждого носка был свой цвет, и у носков в паре был один и тот же цвет и номер пары, которому он принадлежит. Пары пронумерованы различными целыми числами от 1 до n. Кроме того, на каждом носке была маркировка _«Л»_ или _«П»_, обозначающая для левой или правой ноги предназначен этот носок. В каждой паре ровно один носок для левой ноги и ровно один для правой.\n\nПредприимчивый Гарри быстро понял, что носки с такой богатой историей будут отличным подарком для новобранцев, поэтому он решил постирать эти носки и отнести на рынок. Для того, чтобы носки наверняка отстирались, он сложил все носки в одну большую кучу и положил в стиральную машину. По окончании стирки носки выглядели изумительно, но вот беда — все носки оказались перемешаны. Гарри — человек ленивый, поэтому он решил как-то разбить носки на пары так, чтобы в каждой паре был один левый и один правый носок. Конечно, в результате этого носки в одной паре могли оказаться разных цветов. Гарри знает, что среди молодёжи сейчас популярно носить разных цветов на левой и на правой ногах, поэтому Гарри решил презентовать подарок, как «пара разноцветных носков». Однако, в результате перемешивания могла образоваться и пара с двумя носками одинаковых цветов, а в таком случае Гарри обидит кого-нибудь, чего он никак не может допустить.\n\nГарри решил оценить вероятность того, что он никого не обидит. Для этого ему необходимо знать, сколько есть способов разбить носки на пары так, чтобы в каждой паре был один носок для левой ноги и один носок для правой ноги, а также не было пар, в которых оба носка одного цвета. Два разбиения на пары считаются различными, если различаются множества пар, содержащиеся в них. Две пары носков называются различными, если номера пар, из которых взяты левые носки в этих парах, различаются или номера пар, из которых взяты правые носки, различаются. Обратитесь к примерам для лучшего понимания условия. Так как число таких способов может быть очень большим, Гарри интересует остаток от деления количества способов на 109 + 7.\n\nПомогите Гарри, и он не останется в долгу.\n\nВ первой строке задано целое число n — количество пар носков (1 ≤ n ≤ 3 000).\n\nВо второй строке задано n целых чисел a1, a2, ..., an, где ai обозначает цвет носков в паре i (1 ≤ ai ≤ n). Одинаковые цвета обозначены одинаковыми числами, разные — разными.\n\nВыведите одно целое число — остаток от деления числа способов на 109 + 7.\n\nВ первом тестовом примере два способа разбить носки на пары выглядят так (первое число в скобках — номер пары, из которой взят левый носок, второе — правый):\n\nВо втором тестовом примере четыре способа разбить носки на пары:\n\nВ третьем тестовом примере при любом разбиении будет пара, в которой оба носка будут иметь цвет 2, поэтому ответ — 0.\n\nВ четвёртом тестовом примере четыре разбиения выглядят так:\n\n"},{"iden":"входные данные","content":"В первой строке задано целое число n — количество пар носков (1 ≤ n ≤ 3 000).Во второй строке задано n целых чисел a1, a2, ..., an, где ai обозначает цвет носков в паре i (1 ≤ ai ≤ n). Одинаковые цвета обозначены одинаковыми числами, разные — разными."},{"iden":"выходные данные","content":"Выведите одно целое число — остаток от деления числа способов на 109 + 7."},{"iden":"примеры","content":"Входные данные31 2 3Выходные данные2Входные данные41 1 2 2Выходные данные4Входные данные31 2 2Выходные данные0Входные данные41 2 2 3Выходные данные4"},{"iden":"примечание","content":"В первом тестовом примере два способа разбить носки на пары выглядят так (первое число в скобках — номер пары, из которой взят левый носок, второе — правый):  {(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)}. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of sock pairs.  \nLet $ 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 $.  \n\nThere 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 $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 3000 $  \n2. $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nCount the number of bijections $ \\sigma: \\{1, \\dots, n\\} \\to \\{1, \\dots, n\\} $ such that:  \n- Each left sock from pair $ i $ is paired with the right sock from pair $ \\sigma(i) $.  \n- For all $ i $, $ a_i \\neq a_{\\sigma(i)} $ (no monochromatic pair).  \n\nThe 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 $.  \n\n**Formal Objective**  \nCompute:  \n$$\n\\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)\n$$","simple_statement":"Given n pairs of socks, each pair has a color and one left sock and one right sock. After washing, all socks are mixed. Count the number of ways to pair each left sock with a right sock such that no pair has two socks of the same color. Return the answer modulo 10^9 + 7.","has_page_source":false}