CF840C.On the Bench

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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_{pi}·a_{pi+1}$ is not perfect square, holds. Leha wants to find number of right permutations modulo $10^{9}+7$ .

输入格式

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}<=10^{9}$ ) — found array.

输出格式

Output single integer — number of right permutations modulo $10^{9}+7$ .

输入输出样例

输入#1
```
3
1 2 4
```
输出#1
```
2
```
输入#2
```
7
5 2 4 2 4 1 1
```
输出#2
```
144
```

说明/提示

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.

首页