#include <bits/stdc++.h>
using namespace std;
const int MAXN = 605;
const int MOD = 1e9 + 7;
int n;
int dp[MAXN][MAXN];
map<int, int> grp;
vector<int> gg;
int fac[MAXN];
int inv[MAXN];
int C(int x, int y) { return 1LL * fac[x] * inv[y] % MOD * inv[x - y] % MOD; }
void init() {
  memset(dp, 0, sizeof(dp));
  inv[1] = 1;
  inv[0] = 1;
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
  for (int i = 2; i < MAXN; i++)
    inv[i] = 1LL * inv[MOD % i] * (MOD - MOD / i) % MOD;
  for (int i = 1; i < MAXN; i++) inv[i] = 1LL * inv[i - 1] * inv[i] % MOD;
}
int main() {
  init();
  scanf("%d", &n);
  for (int i = 0, x; i < n; i++) {
    scanf("%d", &x);
    for (int j = 2; j * j <= x; j++)
      while (x % (j * j) == 0) x /= j * j;
    grp[x]++;
  }
  for (auto e : grp) {
    gg.push_back(e.second);
  }
  int total = gg[0], sz = gg.size();
  dp[0][gg[0] - 1] = 1;
  for (int i = 1; i < sz; i++) {
    for (int j = 0; j < total; j++) {
      for (int G = 1; G <= gg[i]; G++) {
        for (int P = 0; P <= G && P <= j; P++) {
          if (total + 1 - j >= G - P)
            dp[i][j + gg[i] - P - G] =
                (dp[i][j + gg[i] - P - G] + 1LL * dp[i - 1][j] * C(j, P) % MOD *
                                                C(total + 1 - j, G - P) % MOD *
                                                C(gg[i] - 1, G - 1) % MOD) %
                MOD;
        }
      }
    }
    total += gg[i];
  }
  for (auto it : gg) dp[sz - 1][0] = 1LL * dp[sz - 1][0] * fac[it] % MOD;
  cout << dp[sz - 1][0] << endl;
  return 0;
}
