{"raw_statement":[{"iden":"statement","content":"A year ago on the bench in public park Leha found an array of _n_ numbers. Leha believes that permutation _p_ is right if for all 1 ≤ _i_ < _n_ condition, that _a__p__i_·_a__p__i_ + 1 is not perfect square, holds. Leha wants to find number of right permutations modulo 109 + 7."},{"iden":"input","content":"First line of input data contains single integer _n_ (1 ≤ _n_ ≤ 300) — length of the array.\n\nNext line contains _n_ integers _a_1, _a_2, ... , _a__n_ (1 ≤ _a__i_ ≤ 109) — found array."},{"iden":"output","content":"Output single integer — number of right permutations modulo 109 + 7."},{"iden":"examples","content":"Input\n\n3\n1 2 4\n\nOutput\n\n2\n\nInput\n\n7\n5 2 4 2 4 1 1\n\nOutput\n\n144"},{"iden":"note","content":"For first example:\n\n\\[1, 2, 4\\] — right permutation, because 2 and 8 are not perfect squares.\n\n\\[1, 4, 2\\] — wrong permutation, because 4 is square of 2.\n\n\\[2, 1, 4\\] — wrong permutation, because 4 is square of 2.\n\n\\[2, 4, 1\\] — wrong permutation, because 4 is square of 2.\n\n\\[4, 1, 2\\] — wrong permutation, because 4 is square of 2.\n\n\\[4, 2, 1\\] — right permutation, because 8 and 2 are not perfect squares."}],"translated_statement":[{"iden":"statement","content":"一年前，Leha 在公园的长椅上发现了一个包含 #cf_span[n] 个数字的数组。Leha 认为，如果对于所有 #cf_span[1 ≤ i < n]，都有 #cf_span[api·api + 1] 不是完全平方数，则排列 #cf_span[p] 是“正确”的。Leha 希望求出满足条件的“正确”排列的数量，对 #cf_span[109 + 7] 取模。\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 数组的长度。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... , an] (#cf_span[1 ≤ ai ≤ 109]) —— 找到的数组。\n\n请输出一个整数 —— “正确”排列的数量，对 #cf_span[109 + 7] 取模。\n\n对于第一个例子：\n\n#cf_span[[1, 2, 4]] —— 正确排列，因为 #cf_span[2] 和 #cf_span[8] 都不是完全平方数。\n\n#cf_span[[1, 4, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n\n#cf_span[[2, 1, 4]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n\n#cf_span[[2, 4, 1]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n\n#cf_span[[4, 1, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n\n#cf_span[[4, 2, 1]] —— 正确排列，因为 #cf_span[8] 和 #cf_span[2] 都不是完全平方数。\n\n"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 数组的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... , an] (#cf_span[1 ≤ ai ≤ 109]) —— 找到的数组。"},{"iden":"output","content":"请输出一个整数 —— “正确”排列的数量，对 #cf_span[109 + 7] 取模。"},{"iden":"examples","content":"输入\n3\n1 2 4\n输出\n2\n\n输入\n7\n5 2 4 2 4 1 1\n输出\n144"},{"iden":"note","content":"对于第一个例子：\n#cf_span[[1, 2, 4]] —— 正确排列，因为 #cf_span[2] 和 #cf_span[8] 都不是完全平方数。\n#cf_span[[1, 4, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n#cf_span[[2, 1, 4]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n#cf_span[[2, 4, 1]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n#cf_span[[4, 1, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。\n#cf_span[[4, 2, 1]] —— 正确排列，因为 #cf_span[8] 和 #cf_span[2] 都不是完全平方数。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 300 $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 10^9 $.  \nLet $ S $ be the set of all permutations of $ A $.  \nFor a permutation $ p = (p_1, p_2, \\dots, p_n) \\in S $, define the adjacency product set:  \n$$\nP(p) = \\{ p_i \\cdot p_{i+1} \\mid 1 \\leq i < n \\}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 300 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of permutations $ p \\in S $ such that no element in $ P(p) $ is a perfect square.  \nThat is, compute:  \n$$\n\\left| \\left\\{ p \\in S \\mid \\forall i \\in \\{1, \\dots, n-1\\},\\ p_i \\cdot p_{i+1} \\text{ is not a perfect square} \\right\\} \\right| \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}