#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <const int MOD>
struct ModInt {
  long long x;
  ModInt() : x(0) {}
  ModInt(long long u) : x(u) {
    if (x >= MOD || x < 0) {
      x %= MOD;
      if (x < 0) x += MOD;
    }
  }
  ModInt(const ModInt& m) : x(m.x) {}
  ModInt& operator=(const ModInt& m) {
    x = m.x;
    return *this;
  }
  friend bool operator==(const ModInt& a, const ModInt& b) {
    return a.x == b.x;
  }
  friend bool operator!=(const ModInt& a, const ModInt& b) {
    return a.x != b.x;
  }
  friend bool operator<(const ModInt& a, const ModInt& b) { return a.x < b.x; }
  ModInt& operator+=(const ModInt& m) {
    x += m.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt& m) {
    x -= m.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& m) {
    x = (1ll * x * m.x) % MOD;
    return *this;
  }
  friend ModInt operator-(const ModInt& a) {
    ModInt res(a);
    if (res.x) res.x = MOD - res.x;
    return res;
  }
  friend ModInt operator+(const ModInt& a, const ModInt& b) {
    return ModInt(a) += ModInt(b);
  }
  friend ModInt operator-(const ModInt& a, const ModInt& b) {
    return ModInt(a) -= ModInt(b);
  }
  friend ModInt operator*(const ModInt& a, const ModInt& b) {
    return ModInt(a) *= ModInt(b);
  }
  ModInt f2() { return ModInt(x) += ModInt(x); }
  static long long fp(long long u, long long k) {
    long long res = 1;
    while (k > 0) {
      if (k & 1) res = (res * u) % MOD;
      u = (u * u) % MOD;
      k /= 2;
    }
    return res;
  }
  ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
  ModInt inv() { return ModInt(fp(x, MOD - 2)); }
  static ModInt sign(long long k) {
    return ((k & 1) ? ModInt(MOD - 1) : ModInt(1));
  }
  friend ostream& operator<<(ostream& out, const ModInt& a) {
    return out << a.x;
  }
};
const int m197 = (int)(1e9) + 7;
using Num = ModInt<m197>;
const int upTo = 305;
Num cnt[upTo][upTo];
Num binom[upTo][upTo];
Num fact[upTo];
int nbElem, nbGroup;
vector<int> groups;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int n = 0; n < upTo; ++n) {
    fact[n] = (n ? fact[n - 1] * n : 1);
    for (int k = 0; k <= n; ++k) {
      binom[n][k] = (k ? binom[n - 1][k] + binom[n - 1][k - 1] : 1);
    }
  }
  cin >> nbElem;
  map<vector<int>, int> rawGr;
  for (int iElem = 0; iElem < nbElem; ++iElem) {
    int x;
    cin >> x;
    int cur = x;
    vector<int> setPrime;
    for (int p = 2; p * p <= x; ++p) {
      int expo = 0;
      while (p <= cur && cur % p == 0) {
        cur /= p;
        ++expo;
      }
      if (expo & 1) setPrime.push_back(p);
    }
    if (cur > 1) setPrime.push_back(cur);
    ++rawGr[setPrime];
  }
  for (auto x : rawGr) groups.push_back(x.second);
  nbGroup = ((int)((groups).size()));
  cnt[0][0] = 1;
  int sumPrev = 0;
  for (int iGroup = 0; iGroup < nbGroup; ++iGroup) {
    int size = groups[iGroup];
    Num *prev = cnt[iGroup], *suiv = cnt[iGroup + 1];
    for (int prevRed = 0; prevRed <= sumPrev; ++prevRed) {
      int prevGreen = (sumPrev + 1) - prevRed;
      for (int tkGreen = 0; tkGreen <= min(size, prevGreen); ++tkGreen) {
        for (int tkRed = 0; tkRed <= min(size - tkGreen, prevRed); ++tkRed) {
          if (tkGreen + tkRed == 0) continue;
          int nextRed = prevRed + size - tkGreen - 2 * tkRed;
          Num cRed = binom[prevRed][tkRed];
          Num cGr = binom[prevGreen][tkGreen];
          Num cSplit = binom[size - 1][tkRed + tkGreen - 1];
          suiv[nextRed] += cRed * cGr * cSplit * prev[prevRed];
        }
      }
    }
    sumPrev += size;
  }
  Num res = cnt[nbGroup][0];
  for (int size : groups) res *= fact[size];
  cout << res << "\n";
}
