Non‐Square Product Permutations

Little Keke has a collection of n balls. He labels them from 1 to n and assigns each ball a characteristic value a[i]. Every day he arranges his balls in a new permutation p of {1,2,…,n} with one constraint: for every adjacent pair in the permutation (i.e. for every 1 ≤ i < n), the product a[p_i]×a[p_i+1] must not be a perfect square.

More formally, let each ball’s value be given by a[i] and define for each ball its square‐free part. In other words, for every i we write $$a[i]=y[i]^2\times b[i],$$ where b[i] is square free. It can be shown that the product a[p_i]×a[p_i+1] is a perfect square if and only if b[pi]==b[pi+1]. Thus the permutation p is legal if for every adjacent pair pi and pi+1 we have b[pi] ≠ b[pi+1].

Your task is to compute the number of legal (i.e. valid) permutations modulo \(10^9+7\). Beware: if all balls have the same square‐free part (and n > 1) then no permutation is legal.

If you answer correctly, Little Keke might just give you one of his beloved balls!

inputFormat

The first line contains a single integer n (the number of balls).

The second line contains n space‐separated integers a[1], a[2], …, a[n] where a[i] represents the characteristic value of the i-th ball.

outputFormat

Output a single integer — the number of legal permutations modulo \(10^9+7\).

sample

3
1 1 1

0