English · Original
Chinese · Translation
Formal · Original
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.
## Input
First line of input data contains single integer _n_ (1 ≤ _n_ ≤ 300) — length of the array.
Next line contains _n_ integers _a_1, _a_2, ... , _a__n_ (1 ≤ _a__i_ ≤ 109) — found array.
## Output
Output single integer — number of right permutations modulo 109 + 7.
[samples]
## Note
For first example:
\[1, 2, 4\] — right permutation, because 2 and 8 are not perfect squares.
\[1, 4, 2\] — wrong permutation, because 4 is square of 2.
\[2, 1, 4\] — wrong permutation, because 4 is square of 2.
\[2, 4, 1\] — wrong permutation, because 4 is square of 2.
\[4, 1, 2\] — wrong permutation, because 4 is square of 2.
\[4, 2, 1\] — right permutation, because 8 and 2 are not perfect squares.
一年前，Leha 在公园的长椅上发现了一个包含 #cf_span[n] 个数字的数组。Leha 认为，一个排列 #cf_span[p] 是“正确”的，当且仅当对于所有 #cf_span[1 ≤ i < n]，都有 #cf_span[api·api + 1] 不是完全平方数。Leha 希望求出满足条件的“正确”排列的数量，结果对 #cf_span[109 + 7] 取模。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 数组的长度。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... , an] (#cf_span[1 ≤ ai ≤ 109]) —— 找到的数组。
请输出一个整数 —— “正确”排列的数量，对 #cf_span[109 + 7] 取模。
对于第一个例子：
#cf_span[[1, 2, 4]] —— 正确排列，因为 #cf_span[2] 和 #cf_span[8] 都不是完全平方数。
#cf_span[[1, 4, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[2, 1, 4]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[2, 4, 1]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[4, 1, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[4, 2, 1]] —— 正确排列，因为 #cf_span[8] 和 #cf_span[2] 都不是完全平方数。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300]) —— 数组的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... , an] (#cf_span[1 ≤ ai ≤ 109]) —— 找到的数组。
## Output
请输出一个整数 —— “正确”排列的数量，对 #cf_span[109 + 7] 取模。
[samples]
## Note
对于第一个例子：
#cf_span[[1, 2, 4]] —— 正确排列，因为 #cf_span[2] 和 #cf_span[8] 都不是完全平方数。
#cf_span[[1, 4, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[2, 1, 4]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[2, 4, 1]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[4, 1, 2]] —— 错误排列，因为 #cf_span[4] 是 #cf_span[2] 的平方。
#cf_span[[4, 2, 1]] —— 正确排列，因为 #cf_span[8] 和 #cf_span[2] 都不是完全平方数。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 300 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ 1 \leq a_i \leq 10^9 $.
Let $ S $ be the set of all permutations of $ A $.
For a permutation $ p = (p_1, p_2, \dots, p_n) \in S $, define the *adjacent product set* as $ P(p) = \{ p_i \cdot p_{i+1} \mid 1 \leq i < n \} $.
A permutation $ p $ is called *right* if no element in $ P(p) $ is a perfect square.
**Constraints**
1. $ 1 \leq n \leq 300 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute the number of right permutations modulo $ 10^9 + 7 $:
$$
\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)
$$
API Response (JSON)
{
"problem": {
"name": "C. 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": "CF840C"
},
"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 s...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一年前，Leha 在公园的长椅上发现了一个包含 #cf_span[n] 个数字的数组。Leha 认为，一个排列 #cf_span[p] 是“正确”的，当且仅当对于所有 #cf_span[1 ≤ i < n]，都有 #cf_span[api·api + 1] 不是完全平方数。Leha 希望求出满足条件的“正确”排列的数量，结果对 #cf_span[109 + 7] 取模。\n\n输入的第一行包含一个整数...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 300 $. \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 permu...",
"is_translate": false,
"language": "Formal"
}
]
}