#include <bits/stdc++.h>
using namespace std;
const int N = 400;
const int MOD = (int)1e9 + 7;
int n, x;
long long fac[N], c[N][N];
map<int, int> h;
vector<int> d;
int fix(int x) {
  for (int i = 2; i * i <= x; i++) {
    while (x % (i * i) == 0) {
      x /= i * i;
    }
  }
  return x;
}
void add(long long &x, long long y) {
  x += y;
  x %= MOD;
}
int main() {
  memset(c, 0, sizeof c);
  fac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i - 1] * i % MOD;
  }
  for (int i = 0; i < N; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      if (c[i][j] >= MOD) {
        c[i][j] -= MOD;
      }
    }
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    x = fix(x);
    if (h.count(x) == 0) {
      h[x] = 1;
    } else {
      int y = h[x];
      h[x] = y + 1;
    }
  }
  for (auto it = h.begin(); it != h.end(); it++) {
    d.push_back(it->second);
  }
  sort(d.begin(), d.end());
  int now = d[0] + 1;
  vector<long long> dp(now + 1, 0);
  dp[d[0] - 1] = fac[d[0]];
  for (int i = 1; i < d.size(); i++) {
    vector<long long> ndp(now + d[i] + 1, 0);
    for (int same = 0; same <= now; same++) {
      int dif = now - same;
      if (dp[same] == 0) {
        continue;
      }
      for (int j = 1; j <= d[i] && j <= now; j++) {
        for (int k = 0; k <= same && k <= j; k++) {
          int nsame = same - k + d[i] - j;
          add(ndp[nsame], dp[same] * c[d[i] - 1][j - 1] % MOD * c[same][k] %
                              MOD * c[dif][j - k] % MOD * fac[d[i]]);
        }
      }
    }
    now += d[i];
    dp.swap(ndp);
  }
  printf("%lld\n", dp[0]);
  return 0;
}
