1513: CF840 - C. On the Bench
[Creator : ]
Description
A year ago on the bench in public park Leha found an array ofnnumbers. 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 $10^9+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≤10^9)$ − found array.
Next line contains $n$ integers $a_1,a_2,... ,a_n\ (1≤a_i≤10^9)$ − found array.
Output
Output single integer − number of right permutations modulo $10^9+7$.
Sample 1 Input
3
1 2 4
Sample 1 Output
2
[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.
Sample 2 Input
7
5 2 4 2 4 1 1
Sample 2 Output
144