#include <bits/stdc++.h>
using namespace std;
const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
int n;
int a[303], f[303], cnt[303], sz;
int c[303][303];
int d[303][303];
int ff[303];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    for (int j = 2; j * 1ll * j <= a[i] * 1ll; ++j) {
      while (a[i] % (j * j) == 0) {
        a[i] /= j * j;
      }
    }
  }
  for (int i = 0; i <= n; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % inf;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (!f[i]) {
      f[i] = ++sz;
      for (int j = i; j <= n; ++j) {
        if (a[i] == a[j]) {
          f[j] = f[i];
        }
      }
    }
    ++cnt[f[i]];
  }
  ff[0] = 1;
  for (int i = 1; i <= n; ++i) {
    ff[i] = ff[i - 1] * 1ll * i % inf;
  }
  d[1][0] = 1;
  int tot = 0;
  for (int i = 1; i <= sz; ++i) {
    for (int j = 0; j <= tot; ++j) {
      if (!d[i][j]) {
        continue;
      }
      for (int s = 1; s <= min(tot + 1, cnt[i]); ++s) {
        for (int e = 0; e <= j; ++e) {
          int nxt = (j - e) + (cnt[i] - s);
          int ways = d[i][j] * 1ll * ff[cnt[i]] % inf;
          ways = ways * 1ll * c[cnt[i] - 1][s - 1] % inf;
          ways = ways * 1ll * c[j][e] % inf;
          ways = ways * 1ll * c[tot + 1 - j][s - e] % inf;
          (d[i + 1][nxt] += ways) %= inf;
        }
      }
    }
    tot += cnt[i];
  }
  printf("%d", d[sz + 1][0]);
  return 0;
}
