#include <bits/stdc++.h>
using namespace std;
long long a[302];
int gmap[302];
int g[302];
int sz[302];
long long dp[302][302];
long long fact[302];
long long comb[302][302];
bool mysqrt(long long x) {
  long long s = 1ll, e = 1000000000ll, ans = 0ll;
  while (s <= e) {
    long long m = (s + e) / 2ll;
    if (m * m <= x) {
      s = m + 1ll;
      ans = m;
    } else
      e = m - 1ll;
  }
  return ans * ans == x;
}
int main() {
  ios::sync_with_stdio(0);
  for (int i = 0; i < 302; i++) comb[i][0] = 1;
  for (int i = 1; i < 302; i++) {
    for (int j = 1; j < 302; j++) {
      if (i < j)
        comb[i][j] = 0ll;
      else
        comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % 1000000007ll;
    }
  }
  fact[0] = 1ll;
  for (int i = 1; i < 302; i++) fact[i] = (fact[i - 1] * i) % 1000000007ll;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  int gc = 0;
  for (int i = 0; i < n; i++) {
    if (gmap[i] == 0) {
      gc++;
      for (int j = i; j < n; j++) {
        if (mysqrt(a[i] * a[j])) {
          gmap[j] = gc;
          g[gc]++;
        }
      }
    }
  }
  sz[0] = 1;
  for (int i = 1; i <= gc; i++) sz[i] = sz[i - 1] + g[i];
  dp[0][0] = 1;
  for (int i = 1; i <= sz[gc]; i++) dp[0][i] = 0;
  for (int i = 1; i <= gc; i++) {
    for (int kl = 1; kl <= g[i]; kl++) {
      for (int j = 0; j <= sz[i - 1]; j++) {
        if (dp[i - 1][j] > 0) {
          for (int k = 0; k <= min(kl, j); k++) {
            int l = kl - k, m = sz[i - 1] - j;
            long long adder = (dp[i - 1][j] * comb[j][k]) % 1000000007ll;
            adder = (adder * comb[m][l]) % 1000000007ll;
            adder = (adder * comb[g[i] - 1][kl - 1]) % 1000000007ll;
            dp[i][(j - k) + (g[i] - kl)] += adder;
            dp[i][(j - k) + (g[i] - kl)] %= 1000000007ll;
          }
        }
      }
    }
  }
  long long ans = dp[gc][0];
  for (int i = 1; i <= gc; i++) ans = (ans * fact[g[i]]) % 1000000007ll;
  cout << ans << "\n";
  return 0;
}
