#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll M = 1e9 + 7;
bool is_square(ll x) {
  ll t = sqrt(x);
  return t * t == x;
}
int main() {
  int n;
  cin >> n;
  map<ll, ll> cnt;
  for (int i = 0; i < n; ++i) {
    ll a;
    cin >> a;
    cnt[a]++;
  }
  map<ll, vector<int>> num;
  for (auto& a : cnt) {
    bool update = false;
    for (auto& p : num) {
      if (is_square(a.first * p.first)) {
        num[p.first].push_back(a.second);
        update = true;
        break;
      }
    }
    if (!update) {
      num[a.first].push_back(a.second);
    }
  }
  vector<ll> fact(301);
  fact[0] = 1;
  for (int i = 1; i <= 300; ++i) {
    fact[i] = (fact[i - 1] * i) % M;
  }
  vector<vector<ll>> comb(301, vector<ll>(301));
  for (int i = 0; i < 301; ++i) {
    for (int j = 0; j <= i; ++j) {
      if (i == j || j == 0) {
        comb[i][j] = 1;
      } else {
        comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M;
      }
    }
  }
  vector<vector<ll>> dp(num.size() + 1, vector<ll>(n + 1));
  dp[0][0] = 1;
  ll res = 1;
  ll sum = 0;
  int i = 0;
  for (auto& p : num) {
    int m = accumulate(p.second.begin(), p.second.end(), 0);
    res = (res * fact[m]) % M;
    for (int j = 0; j <= sum; ++j) {
      for (int k = 1; k <= m; ++k) {
        for (int l = 0; l <= min(j, k); ++l) {
          ll t = comb[m - 1][k - 1];
          t = (t * comb[j][l]) % M;
          t = (t * comb[sum - j + 1][k - l]) % M;
          t = (t * dp[i][j]) % M;
          (dp[i + 1][j - l + m - k] += t) %= M;
        }
      }
    }
    sum += m;
    i++;
  }
  res = (res * dp[num.size()][0]) % M;
  cout << res << endl;
}
