#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
const int N = 350, mo = 1e9 + 7;
int n, f[N][N], len, A[N], fac[N], ifac[N], qz[N];
map<int, int> Map;
inline void exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
inline int inv(int a) {
  int x, y;
  exgcd(a, mo, x, y);
  return x >= 0 ? x : x + mo;
}
inline int C(int n, int m) {
  if (m < 0 || m > n) return 0;
  return 1LL * fac[n] * ifac[m] % mo * ifac[n - m] % mo;
}
inline void add(int &a, int b) { a = a + b < mo ? a + b : a + b - mo; }
int main() {
  read(n);
  for (register int i = 1; i <= n; i++) {
    int x;
    read(x);
    for (int j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) x /= j * j;
    }
    Map[x]++;
  }
  while (!Map.empty()) {
    A[++len] = (*Map.begin()).second;
    qz[len] = qz[len - 1] + A[len];
    Map.erase(Map.begin());
  }
  fac[0] = 1;
  for (register int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % mo;
  ifac[n] = inv(fac[n]);
  for (register int i = n - 1; i >= 0; i--)
    ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mo;
  f[0][0] = 1;
  for (register int i = 0; i <= len - 1; i++)
    for (register int j = 0; j <= n + 1; j++)
      if (f[i][j]) {
        int now = f[i][j];
        int red = j, blue = qz[i] - j + 1;
        for (register int a = 0; a <= blue; a++)
          for (register int b = 0; b <= red; b++)
            if (a + b <= A[i + 1])
              add(f[i + 1][j - b + A[i + 1] - a - b],
                  1LL * now * C(blue, a) % mo * C(red, b) % mo *
                      C(A[i + 1] - 1, a + b - 1) % mo * fac[A[i + 1]] % mo);
      }
  cout << f[len][0];
  return 0;
}
