#include <bits/stdc++.h>
using namespace std;
int gi() {
  int a;
  scanf("%d", &a);
  return a;
}
long long gli() {
  long long a;
  scanf("%I64d", &a);
  return a;
}
long long p[10000];
int isp[32000];
int l;
unordered_map<int, int> m;
long long c[304][304];
long long f[304];
long long dp[304][304];
int pw(long long a, int b) {
  if (b == 0) return 1;
  long long x = pw(a, b / 2);
  long long v = (x * x) % 1000000007;
  if (b % 2) return (v * a) % 1000000007;
  return v;
}
int red(int a) {
  for (int i = 0; i < l && a > 1; i++) {
    int v = p[i] * p[i];
    while (a % v == 0) a /= v;
  }
  return a;
}
int main() {
  l = 1;
  p[0] = 2;
  memset(isp, -1, sizeof(isp));
  for (int i = 3; i < 32000; i += 2)
    if (isp[i]) {
      p[l++] = i;
      for (int j = i * 3; j < 32000; j += 2 * i) isp[j] = 0;
    }
  f[0] = 1;
  for (int i = 0; i < 304; i++) {
    if (i) f[i] = (f[i - 1] * i) % 1000000007;
    for (int j = 0; j <= i; j++) {
      long long x = f[i];
      x *= pw(f[j], 1000000007 - 2);
      x %= 1000000007;
      x *= pw(f[i - j], 1000000007 - 2);
      x %= 1000000007;
      c[i][j] = x;
    }
  }
  int n = gi();
  unordered_map<int, int>::iterator it;
  for (int i = 0; i < n; i++) {
    int x = red(gi());
    if ((it = m.find(x)) == m.end())
      m[x] = 1;
    else
      it->second++;
  }
  l = 0;
  for (it = m.begin(); it != m.end(); it++) p[l++] = it->second;
  memset(dp, 0, sizeof(dp));
  long long s = p[0];
  dp[0][s - 1] = f[s];
  for (int i = 1; i < l; i++) {
    long long pv = p[i];
    for (int j = 0; j <= s - i; j++)
      if (dp[i - 1][j])
        for (int np = 1; np <= pv; np++) {
          long long w =
              (((f[pv] * dp[i - 1][j]) % 1000000007) * c[pv - 1][np - 1]) %
              1000000007;
          for (int kill = ((0) > (np - s - 1 + j) ? (0) : (np - s - 1 + j));
               kill <= np && kill <= j; kill++) {
            dp[i][j - kill + pv - np] +=
                (((w * c[j][kill]) % 1000000007) * c[s + 1 - j][np - kill]) %
                1000000007;
            dp[i][j - kill + pv - np] %= 1000000007;
          }
        }
    s += pv;
  }
  printf("%d\n", (int)dp[l - 1][0]);
  return 0;
}
