#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ld eps = 1e-8;
template <class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) {
  return out << "(" << p.first << ", " << p.second << ")";
}
template <size_t i, class T>
ostream& print_tuple_utils(ostream& out, const T& tup) {
  if constexpr (i == tuple_size<T>::value)
    return out << ")";
  else
    return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup),
                                       tup);
}
template <class... U>
ostream& operator<<(ostream& out, const tuple<U...>& tup) {
  return print_tuple_utils<0, tuple<U...>>(out, tup);
}
template <class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type operator<<(
    ostream& out, const Con& container) {
  out << "{";
  for (auto it = container.begin(); it != container.end(); ++it)
    out << (it == container.begin() ? "" : ", ") << *it;
  return out << "}";
}
template <int mod_>
struct modint {
  static constexpr int mod = mod_;
  int x;
  modint(int xx = 0) : x(xx) {}
  modint(ll xx) : x((int)(xx % mod)) {}
  friend inline modint operator+(modint u, const modint& v) { return u += v; }
  modint& operator+=(const modint& o) {
    if ((x += o.x) >= mod) x -= mod;
    return *this;
  }
  friend inline modint operator-(modint u, const modint& v) { return u -= v; }
  modint& operator-=(const modint& o) {
    if ((x -= o.x) < 0) x += mod;
    return *this;
  }
  friend inline modint operator*(modint u, const modint& v) { return u *= v; }
  modint& operator*=(const modint& o) { return *this = modint(1ll * x * o.x); }
  modint pow(ll exp) const {
    modint base = *this, ans = 1;
    for (; exp > 0; exp >>= 1, base *= base)
      if (exp & 1) ans *= base;
    return ans;
  }
  friend inline modint operator/(modint u, const modint& v) { return u /= v; }
  modint& operator/=(const modint& o) { return *this *= o.pow(mod - 2); }
  friend bool operator==(const modint& u, const modint& v) {
    return u.x == v.x;
  }
  friend ostream& operator<<(ostream& out, const modint& u) {
    return out << u.x;
  }
};
using mint = modint<(int)1e9 + 7>;
const int maxn = 696;
mint comb[maxn][maxn];
mint fac[maxn];
void precal() {
  for (int i = (int)(0); i < (int)(maxn); ++i) {
    comb[i][0] = 1;
    for (int f = (int)(1); f < (int)(i + 1); ++f) {
      comb[i][f] = comb[i - 1][f] + comb[i - 1][f - 1];
    }
  }
  fac[0] = 1;
  for (int i = (int)(1); i < (int)(maxn); ++i) fac[i] = fac[i - 1] * i;
}
int reduce_factor(int num) {
  int ans = 1;
  for (int i = 2; i * i <= num; ++i) {
    if (num % i) continue;
    int cnt = 0;
    while (num % i == 0) {
      num /= i;
      cnt ^= 1;
    }
    if (cnt) ans *= i;
  }
  if (num > 1) ans *= num;
  return ans;
}
mint brute(const vector<int>& a) {
  auto is_perfect_sqr = [&](ll num) {
    ll x = (ll)round(sqrt(num));
    return x * x == num;
  };
  vector<int> pos(((int)a.size()));
  for (int i = (int)(0); i < (int)(((int)a.size())); ++i) pos[i] = i;
  mint ans = 0;
  do {
    bool ok = true;
    for (int i = (int)(0); i < (int)(((int)a.size()) - 1); ++i) {
      if (!is_perfect_sqr(1ll * a[pos[i]] * a[pos[i + 1]])) continue;
      ok = false;
      break;
    }
    ans += ok;
  } while (next_permutation((pos).begin(), (pos).end()));
  return ans;
}
mint solve(const vector<int>& a) {
  map<int, int> cnt;
  for (auto i : a) {
    int rd = reduce_factor(i);
    if (0)
      cerr << "["
              "i"
              " = "
           << (i) << "] "
           << "["
              "rd"
              " = "
           << (rd) << "] " << endl;
    cnt[rd]++;
  }
  vector<mint> dp = {1};
  int cnt_have = 0;
  for (auto [val, cur_cnt] : cnt) {
    ;
    if (0)
      cerr << "["
              "val"
              " = "
           << (val) << "] "
           << "["
              "cur_cnt"
              " = "
           << (cur_cnt) << "] " << endl;
    vector<mint> new_dp(((int)a.size()) + 2);
    auto cur_fac = fac[cur_cnt];
    for (int prev_same_pos = (int)(0); prev_same_pos < (int)(((int)dp.size()));
         ++prev_same_pos) {
      if (dp[prev_same_pos] == 0) continue;
      int prev_res_pos = cnt_have + 1 - prev_same_pos;
      for (int cnt_group = (int)(1); cnt_group < (int)(cur_cnt + 1);
           ++cnt_group) {
        ;
        if (0)
          cerr << "["
                  "cnt_group"
                  " = "
               << (cnt_group) << "] " << endl;
        int add_same_pos = cur_cnt - cnt_group;
        for (int choose_same_pos = (int)(0);
             choose_same_pos < (int)(prev_same_pos + 1); ++choose_same_pos) {
          int choose_res_pos = cnt_group - choose_same_pos;
          if (choose_res_pos < 0) break;
          if (choose_res_pos > prev_res_pos) continue;
          int new_same_pos = prev_same_pos + add_same_pos - choose_same_pos;
          mint cur_ans = comb[prev_same_pos][choose_same_pos] *
                         comb[prev_res_pos][choose_res_pos] *
                         comb[cur_cnt - 1][cnt_group - 1] * dp[prev_same_pos];
          if (0)
            cerr << "["
                    "choose_same_pos"
                    " = "
                 << (choose_same_pos) << "] "
                 << "["
                    "new_same_pos"
                    " = "
                 << (new_same_pos) << "] "
                 << "["
                    "cur_ans"
                    " = "
                 << (cur_ans) << "] " << endl;
          new_dp[new_same_pos] += cur_fac * cur_ans;
        }
      }
    }
    swap(dp, new_dp);
    while (dp.size() and dp.back() == 0) dp.pop_back();
    cnt_have += cur_cnt;
    if (0)
      cerr << "["
              "dp"
              " = "
           << (dp) << "] " << endl;
    if (0)
      cerr << "["
              "cnt_have"
              " = "
           << (cnt_have) << "] " << endl;
  }
  return dp[0];
}
mt19937 rng;
void check() {
  while (true) {
    int n = ((int)(rng() >> 1)) % 5 + 1;
    vector<int> a(n);
    for (int i = (int)(0); i < (int)(n); ++i)
      a[i] = ((int)(rng() >> 1)) % 100 + 1;
    ofstream inp("main.inp");
    inp << n << endl;
    for (int i = (int)(0); i < (int)(n); ++i) inp << a[i] << ' ';
    inp << endl;
    auto ans = solve(a);
    auto exp = brute(a);
    inp << "["
           "ans"
           " = "
        << (ans) << "] "
        << "["
           "exp"
           " = "
        << (exp) << "] " << endl;
    inp.close();
    if (ans == exp) {
      cout << "OK" << endl;
      continue;
    }
    cout << "FAILED" << endl;
    exit(0);
  }
}
int main() {
  precal();
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = (int)(0); i < (int)(n); ++i) cin >> a[i];
  cout << solve(a) << endl;
  return 0;
}
