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*_{*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.

Output

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

Note

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.