#include <bits/stdc++.h>
using namespace std;
int n;
int a[310];
int fac[310], inv[310];
int f[2][310];
bool mark[310];
int qpow(int a, int b) {
  int res = 1;
  for (; b; b >>= 1, a = (long long)a * a % 1000000007)
    if (b & 1) res = (long long)res * a % 1000000007;
  return res;
}
int C(int n, int m) {
  return n < m ? 0
               : (long long)fac[n] * inv[m] % 1000000007 * inv[n - m] %
                     1000000007;
}
int main() {
  fac[0] = inv[0] = 1;
  for (int i = 1; i <= 300; ++i) {
    fac[i] = (long long)fac[i - 1] * i % 1000000007;
    inv[i] = qpow(fac[i], 1000000007 - 2);
  }
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  int t = 0;
  f[t][0] = 1;
  int now = 0, res = 1;
  for (int i = 1; i <= n; ++i)
    if (!mark[i]) {
      int cnt = 1;
      for (int j = i + 1; j <= n; ++j) {
        long long tmp = (long long)a[i] * a[j];
        long long sq = sqrt(tmp) + 0.1;
        if (sq * sq == tmp) cnt++, mark[j] = 1;
      }
      for (int i = 0; i <= now; ++i)
        for (int j = 1; j <= cnt; ++j) {
          int tr = (long long)C(cnt - 1, cnt - j) * inv[j] % 1000000007;
          f[t ^ 1][i + j] =
              (f[t ^ 1][i + j] + (long long)tr * f[t][i]) % 1000000007;
        }
      memset(f[t], 0, sizeof(f[t]));
      now += cnt;
      t ^= 1;
      res = (long long)res * fac[cnt] % 1000000007;
    }
  int ans = 0;
  for (int i = 0; i <= now; ++i) {
    int tr = f[t][i];
    if ((now - i) & 1) tr = 1000000007 - tr;
    ans = (ans + (long long)fac[i] * tr) % 1000000007;
  }
  ans = (long long)ans * res % 1000000007;
  printf("%d\n", ans);
  return 0;
}
