#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int maxn = 700;
int p[40005], c = 0;
bool v[40005];
int n, a[maxn];
int b[maxn], sum[maxn];
long long C[maxn][maxn];
long long dp[maxn][maxn];
long long A[maxn];
void pre() {
  for (int i = 2; i < 40005; i++)
    if (!v[i]) {
      p[c++] = i;
      for (int j = 2 * i; j < 40005; j += i) {
        v[j] = 1;
      }
    }
  C[0][0] = 1;
  A[0] = 1;
  for (int i = 1; i < maxn; i++) {
    A[i] = (A[i - 1] * i) % mod;
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
  }
}
int main() {
  pre();
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int now;
    scanf("%d", &now);
    a[i] = 1;
    for (int j = 0; j < c; j++) {
      int k = 0;
      while (now % p[j] == 0) {
        now /= p[j];
        k ^= 1;
      }
      if (k == 1) a[i] *= p[j];
    }
    a[i] *= now;
  }
  sort(a, a + n);
  int n1 = n;
  n = 0;
  for (int i = 0; i < n1; i++) {
    if (i == 0 || a[i] != a[i - 1]) n++;
    b[n]++;
  }
  dp[1][b[1] - 1] = 1;
  for (int i = 1; i < n; i++) {
    sum[i] = sum[i - 1] + b[i];
    for (int j = 0; j < sum[i]; j++) {
      for (int k = 1; k <= b[i + 1]; k++) {
        for (int aa = 0; aa <= k; aa++) {
          int u = b[i + 1] - k + j - aa;
          if (u < 0) continue;
          long long cnt = (C[sum[i] + 1 - j][k - aa] * C[j][aa]) % mod;
          cnt = (cnt * C[b[i + 1] - 1][k - 1]) % mod;
          dp[i + 1][u] = (dp[i + 1][u] + (cnt * dp[i][j]) % mod) % mod;
        }
      }
    }
  }
  long long ret = dp[n][0];
  for (int i = 1; i <= n; i++) {
    ret = (ret * A[b[i]]) % mod;
  }
  printf("%I64d\n", ret);
  return 0;
}
