#include <bits/stdc++.h>
using namespace std;
const int N = 755, P = 1e9 + 7;
int n, m, a[N], b[N], c[N], s[N];
long long comb[N][N], f[N][N], fac[N], factor[N];
void pre() {
  int i, j;
  comb[0][0] = 1ll;
  for (i = 1; i <= n; ++i) {
    comb[i][0] = 1;
    for (j = 1; j <= i; ++j)
      comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % P;
  }
  fac[0] = 1;
  for (i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % P;
}
void solve() {
  int i, sum = 0, j, k, l;
  f[1][c[1] - 1] = 1;
  for (i = 1; i + 1 <= m; ++i) {
    sum += c[i];
    for (j = 0; j + i <= sum; ++j) {
      if (!f[i][j]) continue;
      for (k = 1; k <= min(c[i + 1], sum + 1); ++k) {
        for (l = 0; l <= k; ++l) {
          f[i + 1][j + (c[i + 1] - k) - l] +=
              f[i][j] * comb[j][l] % P * comb[sum + 1 - j][k - l] % P *
              comb[c[i + 1] - k + k - 1][k - 1] % P;
          f[i + 1][j + (c[i + 1] - k) - l] %= P;
        }
      }
    }
  }
  long long ans = f[m][0];
  for (i = 1; i <= m; ++i) (ans *= fac[c[i]]) %= P;
  printf("%lld\n", ans);
}
bool check(long long a, long long b) {
  long long x = round(sqrt(1.0 * a * b)), d;
  for (d = -1; d <= 1; ++d)
    if ((x + d) * (x + d) == a * b) return true;
  return false;
}
int main(int argc, char *argv[]) {
  int i, j, p;
  scanf("%d", &n);
  pre();
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (i = 1; i <= n; ++i) {
    if (!b[i])
      b[i] = ++m;
    else
      continue;
    c[m] = 1;
    for (j = i + 1; j <= n; ++j)
      if (check(a[i], a[j])) ++c[m], b[j] = m;
  }
  solve();
  return 0;
}
