#include <bits/stdc++.h>
using namespace std;
const int nmax = 305;
const long long mod = 1000 * 1000 * 1000 + 7;
long long v[nmax];
long long C[nmax][nmax], dp[2][nmax];
int gr[nmax];
long long fact, n, m, i, j, k, ap;
int use, cnt, tot;
bool pp(long long X) {
  long long rad = sqrt(X);
  return (1LL * rad * rad == X || 1LL * (rad - 1) * (rad - 1) == X ||
          1LL * (rad + 1) * (rad + 1) == X);
}
long long c(int A, int B) { return C[A][B]; }
int main() {
  cin >> n;
  C[0][0] = 1;
  for (i = 1; i <= n; i++) {
    C[i][0] = 1;
    for (j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
  for (i = 1; i <= n; i++) {
    cin >> v[i];
    gr[i] = i;
    for (j = 1; j <= i && gr[i] == i; j++)
      if (pp(v[i] * v[j])) gr[i] = gr[j];
  }
  dp[use][0] = 1;
  for (cnt = 1; cnt <= n; cnt++)
    if (gr[cnt] == cnt) {
      ap = 0;
      fact = 1;
      for (i = 1; i <= n; i++)
        if (gr[i] == cnt) {
          ap++;
          fact = (1LL * fact * ap) % mod;
        }
      for (i = 0; i <= tot; i++) dp[1 - use][i] = 0;
      for (i = 0; i <= tot; i++)
        for (j = 0; j <= i; j++)
          for (k = j; k <= ap; k++)
            dp[1 - use][i - j + ap - k] =
                (dp[1 - use][i - j + ap - k] +
                 (dp[use][i] * ((((1LL * fact * c(tot + 1 - i, k - j)) % mod) *
                                 ((1LL * c(i, j) * c(ap - 1, k - 1)) % mod)) %
                                mod)) %
                     mod) %
                mod;
      use = 1 - use;
      tot += ap;
    }
  cout << dp[use][0];
  return 0;
}
