Problem Description

Xiao Keke is a person with special hobbies. He particularly enjoys collecting various balls and has collected $n$ balls so far.

Xiao Keke is also a person with unique ideas. He numbers all his balls from 1 to $n$ and arranges them into a new permutation every day.

Xiao Keke is a person with special sentiments. He represents the characteristics of each ball with $a[i]$ (note that different balls may have the same $a[i]$).

Xiao Keke is a person who clearly distinguishes between love and hate. He despises square numbers, so he stipulates that a permutation $p$ is valid if, for all $1 ≤ i < n$, $a[p_i] \times a[p_{i+1}]$ is not a square number.

Xiao Keke insists on arranging a new valid permutation every day. One day, he was curious and wanted to know the total number of valid permutations. Xiao Keke is very capable and knows how to calculate it. However, he wants to test you with this problem. Since the number might be too large, you only need to tell him the result modulo $10^9+7$.

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

Input Format

The input consists of two lines:

• The first line contains a positive integer $n$, representing the number of balls Xiao Keke has.
• The second line contains $n$ integers, where the $i$-th integer $a[i]$ represents the characteristics of the ball numbered $i$.

Output Format

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

Sample Input and Output

Sample Input #1

4
2 2 3 4

Sample Output #1

12

Sample Input #2

9
2 4 8 9 12 4 3 6 11

Sample Output #2

99360

Notes

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

Data Range

For 100% of the data: $1 ≤ n ≤ 300$, $1 ≤ a[i] ≤ 10^9$.

This problem consists of 10 test cases, numbered 1 to 10, with additional guarantees for each test case:

见题面 Input 部分

见题面 Output 部分