#include <bits/stdc++.h>
using namespace std;
using llint = long long;
int n, m, a[600], c[600][600], mom[600];
llint f[600][600], inv[600 + 1], fac[600 + 1];
vector<int> g;
int dfs(int i) {
  int res = 1;
  mom[i] = 1;
  for (int j = 0; j < n; ++j) {
    if (c[i][j] == 0 || mom[j] == 1) {
      continue;
    }
    res += dfs(j);
  }
  return res;
}
void pre() {
  fac[0] = fac[1] = 1;
  for (int i = 2; i <= 600; ++i) {
    fac[i] = fac[i - 1] * i;
    if (fac[i] >= 1000000007) {
      fac[i] %= 1000000007;
    }
  }
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= 600; ++i) {
    inv[i] =
        (1000000007 - (1000000007 / i) * inv[1000000007 % i] % 1000000007) %
        1000000007;
  }
  for (int i = 2; i <= 600; ++i) {
    inv[i] *= inv[i - 1];
    if (inv[i] >= 1000000007) {
      inv[i] %= 1000000007;
    }
  }
}
llint ncom(llint k, llint n) {
  if (k > n) {
    return 0;
  }
  llint res = fac[n];
  res *= inv[n - k];
  if (res >= 1000000007) {
    res %= 1000000007;
  }
  res *= inv[k];
  if (res >= 1000000007) {
    res %= 1000000007;
  }
  return res;
}
void update(int i, int p) {
  if (f[i][p] > 0) {
    int s = g[i];
    int n = g[i + 1] - s;
    for (int l = 1; l <= min(n, s + 1); ++l) {
      for (int r = 0; r <= min(p, l); ++r) {
        llint &res = f[i + 1][(p - r) + (n - l)];
        llint t = fac[n] * f[i][p] % 1000000007;
        t = t * ncom(r, p) % 1000000007;
        t = t * ncom(l - r, s + 1 - p) % 1000000007;
        t = t * ncom(n - l, n - 1) % 1000000007;
        res = (res + t) % 1000000007;
      }
    }
  }
}
int main() {
  pre();
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      llint M = (llint)a[i] * a[j];
      llint r = sqrt(M);
      while (r * r < M) {
        r += 1;
      }
      if (r * r == M) {
        c[i][j] = c[j][i] = 1;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    if (mom[i] == 1) {
      continue;
    }
    g.emplace_back(dfs(i));
  }
  m = g.size();
  for (int i = 1; i < m; ++i) {
    g[i] += g[i - 1];
  }
  f[0][g[0] - 1] = fac[g[0]];
  for (int i = 0; i + 1 < m; ++i) {
    for (int j = 0; j < g[i]; ++j) {
      update(i, j);
    }
  }
  cout << f[m - 1][0] << "\n";
}
