#include <bits/stdc++.h>
const int MOD = 1e9 + 7;
const int N = 3e2;
int n, fac[N + 5], ifac[N + 5], c[N + 5][N + 5], f[N + 5][N + 5];
std::map<int, int> mp;
void add(int &x, const int y, const int p = MOD) { (x += y) >= p && (x -= p); }
void sub(int &x, const int y, const int p = MOD) { (x -= y) < 0 && (x += p); }
int mod(const int x, const int p = MOD) {
  return x < 0 ? x + p : x >= p ? x - p : x;
}
int pow(int x, int k, const int p = MOD) {
  int ans = 1;
  for (; k > 0; k >>= 1, x = 1LL * x * x % p) {
    if ((k & 1) == 1) ans = 1LL * ans * x % p;
  }
  return ans;
}
int inv(const int x, const int p = MOD) { return pow(x, p - 2, p); }
void init(int n) {
  for (int i = 0; i <= n; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = mod(c[i - 1][j] + c[i - 1][j - 1]);
    }
  }
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
  ifac[n] = inv(fac[n]);
  for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
}
int main() {
  scanf("%d", &n);
  init(n);
  for (int x, i = 1; i <= n; i++) {
    scanf("%d", &x);
    for (int i = 2; i * i <= x; i++) {
      for (int j = i * i; x % j == 0; x /= j)
        ;
    }
    mp[x]++;
  }
  int m = 0;
  f[0][0] = 1;
  for (const auto &cur : mp) {
    int cnt = cur.second;
    m++;
    for (int j = 1; j <= n; j++) {
      for (int k = 1; k <= j; k++) {
        add(f[m][j], 1LL * f[m - 1][j - k] * c[cnt - 1][k - 1] % MOD *
                         fac[cnt] % MOD * ifac[k] % MOD);
      }
    }
  }
  int ans = 0;
  for (int i = n; i >= 1; i--) {
    if ((n - i) % 2 == 0) {
      add(ans, 1LL * f[m][i] * fac[i] % MOD);
    } else {
      sub(ans, 1LL * f[m][i] * fac[i] % MOD);
    }
  }
  printf("%d\n", ans);
  return 0;
}
