#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<int> v;
int a[302], dp[305][305], cnk[350][350];
void cc() {
  cnk[0][0] = 1;
  for (int i = 1; i <= 302; ++i) {
    cnk[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % mod;
    }
  }
}
bool pp(long long x) {
  int lim = (int)sqrt((double)x);
  return 1LL * lim * lim == x;
}
int main() {
  cc();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    if (v.size() == 0) {
      v.push_back(x);
      a[0]++;
    } else {
      bool amAdaugat = false;
      for (int j = 0; j < v.size(); ++j) {
        if (pp(1LL * v[j] * x)) {
          amAdaugat = true;
          a[j]++;
          break;
        }
      }
      if (amAdaugat == false) {
        a[v.size()]++;
        v.push_back(x);
      }
    }
  }
  n = v.size();
  int prod = 1;
  for (int i = n; i > 0; --i) {
    a[i] = a[i - 1];
    for (int j = 2; j <= a[i]; ++j) {
      prod = (1LL * prod * j) % mod;
    }
  }
  int suma = a[1];
  dp[1][a[1] - 1] = 1;
  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j < suma; ++j) {
      for (int p = 1; p <= a[i]; ++p) {
        for (int h = 0; h <= j && h <= p; ++h) {
          int jnew = j - h + a[i] - p;
          dp[i][jnew] = ((((1LL * dp[i - 1][j] * cnk[j][h]) % mod *
                           cnk[suma + 1 - j][p - h]) %
                          mod * cnk[a[i] - 1][p - 1]) %
                             mod +
                         dp[i][jnew]) %
                        mod;
        }
      }
    }
    suma += a[i];
  }
  printf("%d\n", (1LL * dp[n][0] * prod) % mod);
  return 0;
}
