#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  T w = 1, ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') w = 0;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
  x = w ? x : -x;
}
template <class T, class... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
const int N = 505;
const long long mod = 1e9 + 7;
int n, now;
long long add(long long x, long long y) {
  return (x + y) >= mod ? x + y - mod : x + y;
}
long long sub(long long x, long long y) {
  return (x - y) < 0 ? x - y + mod : ((x - y) >= mod ? x - y - mod : x - y);
}
long long mul(long long x, long long y) {
  long long a = 1ll * x * y % mod;
  return a < 0 ? a += mod : a;
}
struct LL {
  long long a;
  LL(long long _a = 0) : a(_a) {}
  void operator+=(const LL &b) { a = add(a, b.a); }
  void operator-=(const LL &b) { a = sub(a, b.a); }
  void operator*=(const LL &b) { a = mul(a, b.a); }
  LL operator+(const LL &b) { return LL(add(a, b.a)); }
  LL operator*(const LL &b) { return LL(mul(a, b.a)); }
  LL operator^(long long b) {
    LL ans = LL(1);
    for (; b; b >>= 1, *this = LL(a) * LL(a))
      if (b & 1) ans = ans * LL(a);
    return ans;
  }
} C[N][N], Fac[N], dp[N][N];
LL inv(LL b) { return (b ^ (mod - 2)); }
void init() {
  for (register int i = Fac[0].a = 1; i < N; ++i) Fac[i] = Fac[i - 1] * LL(i);
  for (register int i = C[0][0].a = 1; i < N; ++i) {
    C[i][0] = LL(1);
    for (register int j = 1; j < N; ++j)
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1], dp[i][j] = LL(0);
  }
}
map<long long, int> mp;
void add(long long u) {
  for (register int i = 2; i * i <= u; ++i)
    while (!(u % (i * i))) u /= (i * i);
  mp[u]++;
}
int main() {
  init();
  read(n);
  long long x = 0;
  for (register int i = 1; i <= n; ++i) read(x), add(x);
  dp[0][0] = 1;
  int y = 1;
  for (auto u : mp) {
    for (register int k = 1; k <= n; ++k)
      for (register int j = 1; j <= min(u.second, k); ++j)
        dp[y][k] += dp[y - 1][k - j] * C[u.second - 1][j - 1] * Fac[u.second] *
                    inv(Fac[j]);
    y++;
  }
  LL ans = dp[y - 1][n] * Fac[n];
  for (register int i = n - 1, k = 0; i; --i, k ^= 1)
    k & 1 ? ans += dp[y - 1][i] * Fac[i] : ans -= dp[y - 1][i] * Fac[i];
  printf("%lld\n", ans.a);
  return 0;
}
