#include <bits/stdc++.h>
using namespace std;
inline void R(int &v) {
  static char ch;
  v = 0;
  bool p = 0;
  do {
    ch = getchar();
    if (ch == '-') p = 1;
  } while (!isdigit(ch));
  while (isdigit(ch)) {
    v = (v + (v << 2) << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (p) v = -v;
}
int a[305];
inline int xiujian(int now) {
  int ret = 1, t = now, cnt = 0;
  for (int i = 2; i <= sqrt(now); ++i) {
    if (t % i == 0) {
      cnt = 0;
      while (t % i == 0) {
        t /= i;
        ++cnt;
      }
      if (cnt & 1) {
        ret *= cnt;
      }
    }
  }
  ret *= t;
  return ret;
}
int tot, cnt[305], n;
const int mod = 1e9 + 7;
int c[315][315], dp[315][315];
int qz[315];
bool vis[315];
inline long long mul(long long a, long long b) { return (a * b) % mod; }
inline bool check(long long x) {
  long long l = 0, r = 1e9;
  while (l < r - 1) {
    long long m = (l + r) >> 1;
    if (m * m == x) return 1;
    if (m * m < x)
      l = m;
    else
      r = m;
  }
  return 0;
}
int main() {
  R(n);
  int x;
  for (int i = 1; i <= n; ++i) {
    R(a[i]);
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    tot++;
    for (int j = i; j <= n; j++) {
      if (check((long long)a[i] * a[j])) vis[j] = 1, cnt[tot]++;
    }
  }
  for (int i = 0; i < 305; ++i) {
    c[i][0] = c[i][i] = 1;
  }
  for (int i = 1; i < 305; ++i) {
    for (int j = 1; j < 305; ++j) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  int m = cnt[1] - 1;
  dp[1][m] = 1;
  for (int i = 2; i <= tot; m += cnt[i++]) {
    for (int j = 0; j <= m; ++j) {
      if (!dp[i - 1][j]) continue;
      for (int k = 0; k < cnt[i]; ++k) {
        for (int l = 0; l <= min(k + 1, j); ++l) {
          dp[i][j + cnt[i] - l - k - 1] =
              (dp[i][j + cnt[i] - l - k - 1] +
               mul(mul(mul(dp[i - 1][j], c[j][l]), c[m + 2 - j][k + 1 - l]),
                   c[cnt[i] - 1][k])) %
              mod;
        }
      }
    }
  }
  int ans = dp[tot][0];
  int pow1[305];
  pow1[0] = 1;
  for (int i = 1; i <= 305; ++i) {
    pow1[i] = mul(pow1[i - 1], i);
  }
  for (int i = 1; i <= tot; ++i) {
    ans = mul(ans, pow1[cnt[i]]);
  }
  printf("%d\n", ans);
}
