#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e2 + 10;
const long long mod = 1e9 + 7;
int n;
int a[maxn];
vector<int> groups;
int par[maxn];
int sz[maxn];
bool check(long long x) {
  long long y = sqrt(x);
  return y * y == x;
}
int root(int x) {
  if (par[x] == x) return x;
  return root(par[x]);
}
void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y) return;
  if (sz[y] > sz[x]) swap(x, y);
  par[y] = x;
  sz[x] += sz[y];
}
void merge() {
  for (int i = 1; i <= n; ++i) {
    par[i] = i;
    sz[i] = 1;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (check(1LL * a[i] * a[j])) unite(i, j);
  map<int, int> mrk;
  for (int i = 1; i <= n; ++i) {
    int x = root(i);
    if (mrk[x]) continue;
    mrk[x] = true;
    groups.push_back(sz[x]);
  }
}
long long dp[maxn][maxn];
long long c[maxn][maxn];
long long fat[maxn];
long long solve() {
  merge();
  for (int i = 0; i < maxn; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  }
  fat[0] = 1LL;
  for (int i = 1; i < maxn; ++i) fat[i] = (1LL * fat[i - 1] * i) % mod;
  dp[0][groups[0] - 1] = fat[groups[0]];
  int gaps = 1;
  for (int x = 0; x < groups.size() - 1; ++x) {
    gaps += groups[x];
    for (int y = 0; y <= n; ++y) {
      if (!dp[x][y]) continue;
      int good = gaps - y;
      for (int i = 1; i <= groups[x + 1]; ++i)
        for (int bad = 0; bad <= min(y, i); ++bad) {
          int nx = y - bad + groups[x + 1] - i;
          long long comb = 1LL;
          comb = (comb * c[y][bad]) % mod;
          comb = (comb * c[good][i - bad]) % mod;
          comb = (comb * c[groups[x + 1] - 1][i - 1]) % mod;
          comb = (comb * fat[groups[x + 1]]) % mod;
          dp[x + 1][nx] = (dp[x + 1][nx] + dp[x][y] * comb) % mod;
        }
    }
  }
  return dp[groups.size() - 1][0];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  printf("%lld\n", solve());
  return 0;
}
