#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << '{';
  for (int i = (0), __i = (((int)(vec).size())); i < __i; i++) {
    os << vec[i];
    if (i + 1 != ((int)(vec).size())) os << ',';
  }
  os << '}';
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &par) {
  os << '(' << par.first << ',' << par.second << ')';
  return os;
}
int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
template <class T>
T sqr(T x) {
  return x * x;
}
const long long MOD = 1e9 + 7;
long long bin_pow(long long base, long long p) {
  if (p == 1) return base;
  if (p % 2 == 0) {
    long long t = bin_pow(base, p / 2);
    return t * t % MOD;
  } else
    return bin_pow(base, p - 1) * base % MOD;
}
long long inverse_element(long long x) { return bin_pow(x, MOD - 2); }
long long divide(long long a, long long b) {
  return a * inverse_element(b) % MOD;
}
long long mult(long long a, long long b) { return (a * b) % MOD; }
long long dp[333][333];
long long fact[333];
long long comb[333][333];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = 1;
  for (int i = (1), __i = (333); i < __i; i++) fact[i] = mult(fact[i - 1], i);
  for (int i = (0), __i = (333); i < __i; i++) {
    for (int j = (0), __j = (i + 1); j < __j; j++) {
      comb[i][j] = divide(fact[i], mult(fact[j], fact[i - j]));
    }
  }
  int n;
  cin >> n;
  vector<vector<long long>> v;
  for (int i = (0), __i = (n); i < __i; i++) {
    long long a;
    cin >> a;
    bool found = false;
    for (int j = (0), __j = (((int)(v).size())); j < __j; j++) {
      long long t = sqrt(v[j][0] * a);
      if (v[j][0] * a == t * t) {
        v[j].push_back(a);
        found = true;
        break;
      }
    }
    if (!found) v.push_back(vector<long long>({a}));
  }
  dp[0][0] = 1;
  long long spaces = 1;
  for (int x = (0), __x = (((int)(v).size())); x < __x; x++) {
    for (int ij = (1), __ij = (((int)(v[x]).size()) + 1); ij < __ij; ij++) {
      for (int y = (0), __y = (spaces + 1); y < __y; y++) {
        if (dp[x][y] > 0)
          for (int j = (0), __j = (min(ij, y) + 1); j < __j; j++) {
            int i = ij - j;
            int z = spaces - y;
            dp[x + 1][(y - j) + (((int)(v[x]).size()) - ij)] +=
                mult(dp[x][y], mult(comb[y][j], comb[z][i])) *
                mult(comb[((int)(v[x]).size()) - 1][ij - 1],
                     fact[((int)(v[x]).size())]);
            dp[x + 1][(y - j) + (((int)(v[x]).size()) - ij)] %= MOD;
          }
      }
    }
    spaces += ((int)(v[x]).size());
  }
  cout << dp[((int)(v).size())][0];
  return 0;
}
