#include <bits/stdc++.h>
using namespace std;
namespace RA {
int r(int p) { return 1ll * rand() * rand() % p; }
int r(int L, int R) { return r(R - L + 1) + L; }
}  // namespace RA
const int N = 500, P = 1e9 + 7;
int n, a[N], c[N][N], fac[N], f[N], g[N], tot;
bool vis[N];
vector<int> v;
bool square(long long x) {
  long long y = sqrt(x);
  while (y * y < x) ++y;
  while (y * y > x) --y;
  if (y * y == x) return 1;
  return 0;
}
int main() {
  cin >> n;
  for (int i = (1); i <= (n); ++i) cin >> a[i];
  c[0][0] = 1;
  for (int i = (1); i <= (n); ++i) {
    c[i][0] = 1;
    for (int j = (1); j <= (i); ++j)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
  }
  fac[0] = 1;
  for (int i = (1); i <= (n); ++i) fac[i] = fac[i - 1] * 1ll * i % P;
  for (int i = (1); i <= (n); ++i)
    if (!vis[i]) {
      int cnt = 1;
      for (int j = (i + 1); j <= (n); ++j)
        if (!vis[j] && square(a[i] * 1ll * a[j])) vis[j] = 1, ++cnt;
      v.push_back(cnt);
    }
  f[0] = 1;
  auto add = [](int &x, long long y) { x = (x + y) % P; };
  for (int x : v) {
    for (int i = (0); i <= (x - 1); ++i) {
      long long coef = c[x - 1][i] * 1ll * fac[x] % P;
      for (int j = (0); j <= (tot); ++j) {
        add(g[i + j],
            f[j] * coef % P * c[x - i + (tot + 1 - j - 1)][tot + 1 - j - 1]);
      }
    }
    tot += x;
    for (int i = (0); i <= (tot); ++i) f[i] = g[i], g[i] = 0;
  }
  int ans = 0;
  for (int i = (0); i <= (tot); ++i) {
    int coef = i % 2 ? -1 : 1;
    add(ans, coef * f[i]);
  }
  add(ans, P);
  cout << ans << endl;
  return 0;
}
