#include <bits/stdc++.h>
using namespace std;
long long int ar1[305];
class UnionFind {
 private:
  vector<int> p, rank, setSize;
  int numSets;

 public:
  UnionFind(int N) {
    setSize.assign(N, 1);
    numSets = N;
    rank.assign(N, 0);
    p.assign(N, 0);
    for (int i = 0; i < N; i++) p[i] = i;
  }
  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (!isSameSet(i, j)) {
      numSets--;
      int x = findSet(i), y = findSet(j);
      if (rank[x] > rank[y]) {
        p[y] = x;
        setSize[x] += setSize[y];
      } else {
        p[x] = y;
        setSize[y] += setSize[x];
        if (rank[x] == rank[y]) rank[y]++;
      }
    }
  }
  int numDisjointSets() { return numSets; }
  int sizeOfSet(int i) { return setSize[findSet(i)]; }
};
long long int bigmod(long long int a, long long int p) {
  if (p == 1) return a % 1000000007;
  if (p % 2) return (a * bigmod(a, p - 1)) % 1000000007;
  long long int c = bigmod(a, p / 2);
  return (c * c) % 1000000007;
}
long long int factn[1000], invfactn[1000];
long long int factm[1000], invfactm[1000];
void init(int n) {
  factn[0] = 1;
  invfactn[0] = 1;
  for (long long int i = 1; i <= n; i++)
    factn[i] = (factn[i - 1] * i) % 1000000007;
  for (long long int i = 1; i <= n; i++)
    invfactn[i] = (invfactn[i - 1] * bigmod(i, 1000000007 - 2)) % 1000000007;
  return;
}
void init2(int n) {
  factm[0] = 1;
  invfactm[0] = 1;
  for (long long int i = 1; i <= n; i++)
    factm[i] = (factm[i - 1] * i) % 1000000007;
  for (long long int i = 1; i <= n; i++)
    invfactm[i] = (invfactm[i - 1] * bigmod(i, 1000000007 - 2)) % 1000000007;
  return;
}
long long int nCr(int n, int r) {
  if (n < 0) return 0;
  if (n < r) return 0;
  long long int res = (invfactn[n - r] * invfactn[r]) % 1000000007;
  res = (res * factn[n]) % 1000000007;
  return res;
}
long long int nPr2(int n, int r) {
  long long int res = (invfactm[n - r]) % 1000000007;
  res = (res * factm[n]) % 1000000007;
  return res;
}
vector<int> vec1;
long long int dp[305][305];
long long int call(int i, int bad, int n, int total) {
  if (i == n) return (bad == 0);
  long long int &ret = dp[i][bad];
  if (ret != -1) return ret;
  ret = 0;
  int cur_total = total + vec1[i];
  int gaps = total + 1;
  for (int split = 1; split <= min(gaps, vec1[i]); split++) {
    for (int chosen_bad_gap = 0; chosen_bad_gap <= min(bad, split);
         chosen_bad_gap++) {
      int good_gaps = gaps - chosen_bad_gap;
      int new_bad = bad - chosen_bad_gap + vec1[i] - split;
      int good_splits = split - chosen_bad_gap;
      long long int temp = 1;
      temp = (nCr(vec1[i] - 1, split - 1) * factn[vec1[i]]) % 1000000007;
      temp = (temp * nCr(bad, chosen_bad_gap)) % 1000000007;
      temp = (temp * nCr(gaps - bad, good_splits)) % 1000000007;
      temp = (temp * call(i + 1, new_bad, n, total + vec1[i])) % 1000000007;
      ret = (ret + temp) % 1000000007;
    }
  }
  return ret;
}
int main() {
  map<int, int> Map;
  int n, k;
  cin >> n;
  for (int i = 0; i < n; i++) {
    scanf("%d", &ar1[i]);
    Map[ar1[i]]++;
  }
  UnionFind uf(n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      double a = sqrt(ar1[i] * ar1[j]);
      if (floor(a) == ceil(a)) uf.unionSet(i, j);
    }
  init(n + 2);
  int s = uf.numDisjointSets();
  set<int> S;
  for (int i = 0; i < n; i++) S.insert(uf.findSet(i));
  vector<int> x;
  for (set<int>::iterator it = S.begin(); it != S.end(); it++) x.push_back(*it);
  for (int i = 0; i < x.size(); i++) vec1.push_back(uf.sizeOfSet(x[i]));
  memset(dp, -1, sizeof(dp));
  long long int res = call(0, 0, x.size(), 0);
  printf("%lld\n", res);
  return 0;
}
