#include <bits/stdc++.h>
using namespace std;
const int N = 302, mod = 1e9 + 7;
long long dp[N][N], a[N], prime[N], fac[N], x, y, g, n, b[N], sb = 1, c1, c2,
                                                              cnt, sfr;
long long xgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1, gcd = xgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (long long)(a / b) * y1;
  return gcd;
}
long long entekhab(long long r, long long n) {
  if (r > n) return 0;
  if (r == 0) return 1;
  long long ans = 1;
  ans = fac[n];
  x = 1, y = 1, g = xgcd(fac[r], mod, x, y);
  ans = (ans * ((x + mod) % mod)) % mod;
  x = 1, y = 1, g = xgcd(fac[n - r], mod, x, y);
  ans = ((ans * ((x + mod) % mod))) % mod;
  return ans;
}
int main() {
  fac[0] = 1;
  for (long long i = 1; i < N; i++) fac[i] = (fac[i - 1] * i) % mod;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    for (int j = 2; j * j <= a[i]; j++) {
      while (a[i] % (j * j) == 0) a[i] = a[i] / (j * j);
    }
  }
  sort(a, a + n);
  for (long long i = 0; i < n; i++) {
    if (i != 0 && a[i] != a[i - 1]) {
      sb++;
      b[sb]++;
    } else
      b[sb]++;
  }
  a[0] = 0, n = sb + 1;
  for (long long i = 1; i < n; i++) a[i] = b[i] + a[i - 1];
  dp[1][b[1] - 1] = 1;
  for (long long i = 2; i < n; i++) {
    for (long long j = 0; j < a[i]; j++) {
      for (long long k = 0; k < a[i - 1]; k++) {
        for (long long l = max(sfr, k - j); l < min(k, b[i]) + 1; l++) {
          c1 = b[i] - l;
          c2 = j - (k - l);
          c1 -= c2;
          if (c1 >= 0) {
            cnt = (((dp[i - 1][k] * entekhab(l, k)) % mod) *
                   entekhab(c1, a[i - 1] - k + 1)) %
                  mod;
            c1 += l;
            cnt = (cnt * entekhab(c1 - 1, c1 + c2 - 1)) % mod;
            dp[i][j] = (dp[i][j] + cnt) % mod;
          }
        }
      }
    }
  }
  for (long long i = 0; i < n; i++)
    dp[n - 1][0] = (dp[n - 1][0] * fac[b[i]]) % mod;
  cout << dp[n - 1][0];
}
