#include <bits/stdc++.h>
using namespace std;
constexpr int N = 300 + 10;
constexpr int MOD = 1e9 + 7;
long long n, a[N], c[N][N], dp[N][N], total, sz[N], fact[N], p, local;
set<int> st;
map<int, int> mp;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int 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] /= j * j;
    }
    st.insert(a[i]);
    mp[a[i]]++;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (j == 0 || j == i) {
        c[i][j] = 1;
        continue;
      }
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
    }
  }
  fact[0] = 1;
  for (int i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % MOD;
  for (auto i : st) sz[p++] = mp[i];
  dp[0][sz[0] - 1] = fact[sz[0]];
  total = sz[0];
  for (int i = 1; i < p; i++) {
    for (int k = 1; k <= min(sz[i], total + 1); k++) {
      for (int j = 0; j < total + sz[i]; j++) {
        for (int l = 0; l <= k; l++) {
          local =
              (c[j - sz[i] + k + l][l] * dp[i - 1][j - sz[i] + k + l]) % MOD;
          local *= c[total + 1 - j + sz[i] - k - l][k - l];
          local %= MOD;
          local *= c[sz[i] - 1][k - 1];
          local %= MOD;
          local *= fact[sz[i]];
          local %= MOD;
          dp[i][j] += local;
          dp[i][j] %= MOD;
        }
      }
    }
    total += sz[i];
  }
  cout << dp[p - 1][0] << '\n';
  return 0;
}
