Description

Xiao Keke is a person with special hobbies. He especially likes collecting all kinds of balls, and has collected $n$ balls so far.

Xiao Keke also has special ideas. He numbers all his balls from 1 to $n$, and arranges the balls into a brand-new permutation every day.

Xiao Keke also has special feelings. He represents the attribute of each ball by $a[i]$ (note that $a[i]$ can be the same for different balls).

Xiao Keke is a person of clear likes and dislikes. He hates perfect squares, so he stipulates: for a permutation $p$, for all $1 \le i < n$, $a[p_i] \times a[p_{i+1}]$ is not a perfect square; only such a permutation $p$ is valid.

He keeps arranging a brand-new valid permutation every day. One day, on a whim, he wants to know the number of all valid permutations. Xiao Keke is very strong and certainly knows how to compute it. However, he wants to test you with this problem. This number can be very large, so you only need to tell him the number of valid permutations modulo $10^9+7$.

Can you answer Xiao Keke’s question correctly? If you can, he might even give you a ball.

Input Format

The input has two lines:

• The first line contains a positive integer $n$, the number of balls that Xiao Keke has.
• The second line contains $n$ integers; the $i$-th integer $a[i]$ denotes the attribute of the ball with index $i$.

Output Format

Output one line containing a single positive integer, the number of valid permutations modulo $10^9+7$ (i.e., 1000000007).

4
2 2 3 4

12

9
2 4 8 9 12 4 3 6 11

99360

Hint

[Sample 1 Explanation]
There are 12 valid permutations:

1,3,2,4
2,3,1,4
3,1,4,2
3,2,4,1
1,3,4,2
2,3,4,1
1,4,2,3
2,4,1,3
4,1,3,2
4,2,3,1
1,4,3,2
2,4,3,1

Constraints

For 100% of the testdata: $1 \le n \le 300$, $1 \le a[i] \le 10^9$.

This problem has 10 test points, numbered 1-10; each test point additionally guarantees the following:

Translated by ChatGPT 5