#include <bits/stdc++.h>
using namespace ::std;
const long long maxn = 320;
const long long mod = 1e9 + 7;
long long dp[maxn][maxn];
long long fuc[maxn];
long long qqq[maxn][maxn][maxn];
long long a[maxn];
long long b[maxn];
long long d[maxn];
bool morab(long long a) {
  long long b = sqrt(a) - 7;
  for (long long i = 0; i < 14; i++) {
    if (b * b == a) {
      return 1;
    }
    b++;
  }
  return 0;
}
int main() {
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  fuc[0] = 1;
  for (long long i = 1; i < maxn; i++) {
    fuc[i] = (fuc[i - 1] * i) % mod;
  }
  long long k = 1;
  b[0] = 0;
  d[0] = 1;
  for (long long i = 1; i < n; i++) {
    bool p = 1;
    for (long long j = 0; j < i; j++) {
      if (morab(a[i] * a[j])) {
        b[i] = b[j];
        d[b[i]]++;
        p = 0;
        break;
      }
    }
    if (p) {
      b[i] = k;
      d[k]++;
      k++;
    }
  }
  long long ans = 1;
  for (long long i = 0; i < k; i++) {
    b[i] = d[i];
  }
  for (long long i = 0; i < k; i++) {
    ans *= fuc[b[i]];
    ans %= mod;
  }
  sort(b, b + k);
  {
    qqq[0][0][0] = 1;
    for (long long u = 1; u < maxn; u++) {
      qqq[u][0][u] = 1;
    }
    for (long long c = 1; c < 2 * maxn; c++) {
      for (long long a = 1; a < c && a < maxn; a++) {
        long long b = c - a;
        if (b < maxn && b > 0) {
          for (long long u = 1; u < maxn; u++) {
            qqq[a][b][u] = (qqq[b][a - 1][u - 1] + qqq[a - 1][b][u - 1] +
                            qqq[b][a - 1][u]) %
                           mod;
          }
        }
      }
    }
  }
  dp[0][b[0]] = 2;
  dp[0][b[0] + 1] = 1;
  dp[0][b[0] - 1] = 1;
  for (long long i = 1; i < k; i++) {
    for (long long j = 0; j < maxn; j++) {
      for (long long u = b[i] + j; u >= 1; u--) {
        dp[i][j] += ((qqq[j][b[i]][u] + qqq[b[i]][j][u]) * dp[i - 1][u]) % mod;
        dp[i][j] %= mod;
      }
    }
  }
  cout << (dp[k - 1][0] * ans) % mod;
}
