#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)307;
const int infint = (long long)1e9;
const long long inf = (long long)1e18;
long long n, a[MAXN], type[MAXN], sm[MAXN], C[MAXN][MAXN], dp[MAXN][MAXN],
    fact[MAXN];
unordered_map<int, int> M, hsh;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    for (int j = 4 * 10000; j >= 2; j--)
      if (a[i] % (j * j) == 0) a[i] /= j * j;
    M[a[i]]++;
  }
  int t = 0;
  for (auto u : M) hsh[u.first] = t++;
  for (int i = 0; i < n; i++) a[i] = hsh[a[i]];
  for (int i = 0; i < n; i++) type[a[i]]++;
  for (int i = 0; i < t; i++) {
    sm[i] = type[i];
    if (i != 0) sm[i] += sm[i - 1];
  }
  fact[0] = 1;
  for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
  C[0][0] = 1;
  for (int i = 1; i < MAXN; i++)
    for (int j = 0; j <= i; j++)
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  dp[0][type[0] - 1] = 1;
  for (int i = 0; i < t - 1; i++)
    for (int j = 0; j < sm[i]; j++)
      for (int p = 1; p <= min(sm[i] + 1, type[i + 1]); p++)
        for (int k = 0; k <= min(p, j); k++) {
          int nw = j + (type[i + 1] - p) - k;
          dp[i + 1][nw] += C[j][k] * C[sm[i] + 1 - j][p - k] % MOD *
                           C[type[i + 1] - 1][p - 1] % MOD * dp[i][j] % MOD,
              dp[i + 1][nw] %= MOD;
        }
  long long ans = dp[t - 1][0];
  for (int i = 0; i < t; i++) ans = ans * fact[type[i]] % MOD;
  cout << ans;
}
