{"problem":{"name":"E. On the Bench","description":{"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 s","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF841E"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nFirst 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.\n\n## Output\n\nOutput single integer — number of right permutations modulo 109 + 7.\n\n[samples]\n\n## Note\n\nFor 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 数组的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... , an] (#cf_span[1 ≤ ai ≤ 109]) —— 找到的数组。\n\n## Output\n\n请输出一个整数 —— “正确”排列的数量，对 #cf_span[109 + 7] 取模。\n\n[samples]\n\n## Note\n\n对于第一个例子：\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] 都不是完全平方数。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF841E","tags":[],"sample_group":[["3\n1 2 4","2"],["7\n5 2 4 2 4 1 1","144"]],"created_at":"2026-03-03 11:00:39"}}