#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000 * 1000 * 1000 + 7;
int n, t;
int a[512];
long long fact[1024];
long long pascal[1024][1024];
map<int, int> cp;
vector<int> v;
vector<int> s;
long long memo[512][512];
long long ways(int id_coul, int nb_prob) {
  if (memo[id_coul][nb_prob] != -1LL) return memo[id_coul][nb_prob];
  long long ans = 0;
  for (int problemes_avant = 0; problemes_avant < s[id_coul - 1];
       problemes_avant++) {
    long long terme = 0;
    int possibilites_sans_probleme = s[id_coul - 1] + 1 - problemes_avant;
    for (int p = 0; p <= min(v[id_coul], problemes_avant); p++) {
      long long f = pascal[problemes_avant][p];
      int problemes_restants = problemes_avant - p;
      int problemes_a_creer = nb_prob - problemes_restants;
      if (problemes_a_creer >= 0) {
        int a_placer = v[id_coul] - p;
        int nb_emplacements = a_placer - problemes_a_creer;
        if ((0 <= nb_emplacements) &&
            (nb_emplacements <= possibilites_sans_probleme))
          f = (f * pascal[possibilites_sans_probleme][nb_emplacements]) % MOD;
        else
          f = 0;
        int tot_emplacements = p + nb_emplacements;
        int restants = v[id_coul] - tot_emplacements;
        if (tot_emplacements && (restants >= 0))
          f = (f * pascal[tot_emplacements + restants - 1][restants]) % MOD;
        else
          f = 0;
      } else
        f = 0;
      terme = (terme + f) % MOD;
    }
    ans = (ans + terme * ways(id_coul - 1, problemes_avant)) % MOD;
  }
  return memo[id_coul][nb_prob] = ans;
}
int main() {
  fact[0] = 1;
  pascal[0][0] = 1;
  for (long long i = 1; i < 1024; i++) {
    fact[i] = (fact[i - 1] * i) % MOD;
    pascal[i][0] = pascal[i][i] = 1;
    for (int j = 1; j < i; j++)
      pascal[i][j] = (pascal[i - 1][j - 1] + pascal[i - 1][j]) % MOD;
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    int k = 1;
    for (int p = 2; p * p <= a[i]; p++) {
      if (a[i] % p == 0) {
        int parity = 0;
        while (a[i] % p == 0) {
          a[i] /= p;
          parity++;
        }
        if (parity % 2) k *= p;
      }
    }
    k *= a[i];
    cp[k]++;
  }
  long long ans = 1;
  for (map<int, int>::iterator it = cp.begin(); it != cp.end(); it++) {
    ans = (ans * fact[it->second]) % MOD;
    v.push_back(it->second);
    s.push_back((s.empty() ? 0 : s.back()) + v.back());
  }
  t = v.size();
  memset(memo, -1, sizeof(memo));
  for (int i = 0; i < n; i++) memo[0][i] = 0;
  memo[0][v[0] - 1] = 1;
  printf("%lld\n", (ans * ways(t - 1, 0)) % MOD);
  return 0;
}
