#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
const int MAX_N = 305;
int N, a[MAX_N], f[MAX_N][MAX_N], C[MAX_N][MAX_N], g[MAX_N][MAX_N];
int bel[MAX_N], cnt;
vector<int> pot[MAX_N];
void Pls(int &x, int y) {
  x += y;
  if (x >= Mod) x -= Mod;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) scanf("%d", a + i);
  for (int i = 1; i <= N; i++) {
    bool flag = 1;
    for (int j = 1; j < i; j++) {
      long long t = 1ll * a[j] * a[i], v = sqrt(t);
      if (1ll * v * v == t) {
        pot[bel[i] = bel[j]].push_back(a[i]);
        flag = 0;
        break;
      }
    }
    if (flag) bel[i] = ++cnt, pot[cnt].push_back(a[i]);
  }
  for (int i = C[0][0] = 1; i <= N; i++)
    for (int j = C[i][0] = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
  f[0][0] = g[0][0] = 1;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i; j++)
      g[i][j] =
          (1ll * g[i - 1][j] * (i + j - 1) + 1ll * j * g[i - 1][j - 1]) % Mod;
  for (int i = 1, sum = 0; i <= cnt; i++) {
    int n = pot[i].size();
    for (int j = 0; j <= sum; j++)
      for (int k = 1; k <= n; k++)
        for (int l = 0; l <= j; l++)
          Pls(f[i][j + n - k - l], 1ll * f[i - 1][j] * g[n][k] % Mod * C[j][l] %
                                       Mod * C[sum + 1 - j][k - l] % Mod);
    sum += n;
  }
  printf("%d\n", f[cnt][0]);
  return 0;
}
