#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
struct Union_Find {
  vector<int> data;
  Union_Find(int size) : data(size, -1) {}
  bool Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    bool is_union = (x != y);
    if (is_union) {
      if (data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return is_union;
  }
  int Find(int x) {
    if (data[x] < 0) {
      return x;
    } else {
      data[x] = Find(data[x]);
      return data[x];
    }
  }
  bool same(int x, int y) { return Find(x) == Find(y); }
  int size(int x) { return -data[Find(x)]; }
};
bool square(ll x) {
  ll ok = 0, ng = 1000000001;
  while (ng - ok > 1) {
    ll mid = (ng + ok) / 2;
    if (mid * mid <= x)
      ok = mid;
    else
      ng = mid;
  }
  return ok * ok == x;
}
ll f[305], fi[305], dp[305][305][305];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> a(n);
  map<ll, ll> cnt;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  Union_Find uf(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (square(a[i] * a[j])) {
        uf.Union(i, j);
      }
    }
  }
  map<ll, vector<ll> > memo;
  for (int i = 0; i < n; i++) {
    memo[uf.Find(i)].push_back(a[i]);
  }
  int used = 0;
  dp[0][0][0] = 1;
  for (auto p : memo) {
    for (int i = 0; i < p.second.size(); i++) {
      for (int k = 0; k <= i * 2; k++) {
        for (int j = 0; j <= used - 2 * i + k + 1; j++) {
          (dp[used + 1][j][k + 1] += dp[used][j][k] * (2 * i - k)) %= MOD;
          if (j > 0) (dp[used + 1][j - 1][k] += dp[used][j][k] * j) %= MOD;
          int rest = used - 2 * i + k - j + 1;
          if (rest > 0) (dp[used + 1][j][k] += dp[used][j][k] * rest) %= MOD;
        }
      }
      used++;
    }
    for (int j = 0; j <= 300; j++) {
      for (int k = 1; k <= 300; k++) {
        (dp[used][j + k][0] += dp[used][j][k]) %= MOD;
        dp[used][j][k] = 0;
      }
    }
  }
  cout << dp[n][0][0] << endl;
  return 0;
}
