#include <bits/stdc++.h>
using namespace std;
long long n, a[305];
long long b[303], sz, ck[303], dp[303][303];
const long long mod = 1e9 + 7;
long long fac[307], C[303][303];
int main() {
  fac[0] = 1;
  for (long long i = 1; i <= 300; i++) fac[i] = (i * fac[i - 1]) % mod;
  C[0][0] = 1;
  C[1][0] = 1, C[1][1] = 1;
  for (long long i = 2; i <= 300; i++) {
    C[i][0] = 1;
    for (long long j = 1; j <= 300; j++) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
      C[i][j] %= mod;
    }
  }
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < n; i++) {
    if (ck[i] == 0) {
      ck[i] = ++sz;
      b[sz]++;
      for (long long j = i + 1; j < n; j++) {
        long long p = a[i] * a[j];
        long long q = sqrt(p);
        q *= q;
        if (p == q) ck[j] = sz, b[sz]++;
      }
    }
  }
  dp[1][b[1] - 1] = 1;
  long long total = b[1];
  long long ans = fac[b[1]];
  for (long long i = 1; i < sz; i++) {
    for (long long j = 0; j <= n; j++) {
      if (dp[i][j] != 0) {
        for (long long s = 1, sr = min(b[i + 1], total + 1) + 1; s < sr; s++) {
          for (long long d = 0, dr = min(j, s) + 1; d < dr; d++) {
            dp[i + 1][j - d + b[i + 1] - s] +=
                (((C[b[i + 1] - 1][s - 1] * C[j][d]) % mod *
                  C[total + 1 - j][s - d]) %
                 mod * dp[i][j]) %
                mod;
            dp[i + 1][j - d + b[i + 1] - s] %= mod;
          }
        }
      }
    }
    ans *= fac[b[i + 1]];
    ans %= mod;
    total += b[i + 1];
  }
  ans *= dp[sz][0];
  ans %= mod;
  cout << ans << endl;
  return 0;
}
