#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void err(const char *x, Arg1 &&arg1) {
  cerr << x << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void err(const char *x, Arg1 &&arg1, Args &&...args) {
  cerr.write(x, strchr(x, ',') - x) << " = " << arg1 << ",",
      err(strchr(x, ',') + 1, args...);
}
template <typename T>
inline void Int(T &n) {
  int f = 1, ch = getchar();
  for (n = 0; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
  n = n * f;
}
template <typename T>
T gcd(T a, T b) {
  return !b ? a : gcd(b, a % b);
}
template <typename T>
inline void umin(T &a, T b) {
  a = a < b ? a : b;
}
template <typename T>
inline void umax(T &a, T b) {
  a = a > b ? a : b;
}
template <typename T, typename W>
inline void Int(T &x, W &y) {
  Int(x), Int(y);
}
template <typename T, typename W, typename Q>
void Int(T &x, W &y, Q &z) {
  Int(x, y), Int(z);
}
const int N = 300 + 7;
const int inf = 1e9 + 7;
int a[N];
int group[N];
long long fac[N];
long long ways[N][N];
long long C[N][N];
void binomial_table() {
  C[0][0] = 1;
  for (int i = 1; i < N; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
      if (C[i][j] >= 1000000007LL) {
        C[i][j] -= 1000000007LL;
      }
    }
  }
}
void factorial_table() {
  fac[0] = 1;
  for (int i = 1; i < N; ++i) {
    fac[i] = (fac[i - 1] * i) % 1000000007LL;
  }
}
inline long long sq(long long x) { return x * x; }
inline bool is_perfect_square(long long n) {
  long long r = sqrtl(1.0 * n);
  return sq(r) == n || sq(r + 1) == n || sq(r - 1) == n;
}
long long mult(long long x, long long y) { return (x * y) % 1000000007LL; }
int solver() {
  binomial_table();
  factorial_table();
  int n;
  Int(n);
  for (int i = 1; i <= n; ++i) {
    Int(a[i]);
  }
  int ii = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] > 0) {
      ++ii;
      ++group[ii];
      for (int j = i + 1; j <= n; ++j) {
        if (a[j] > 0 && is_perfect_square(1LL * a[i] * a[j])) {
          group[ii]++;
          a[j] = 0;
        }
      }
    }
  }
  n = ii;
  ways[0][0] = 1;
  int spaces = 1;
  for (int grp = 0; grp < n; ++grp) {
    for (int bad = 0; bad <= spaces; ++bad) {
      if (ways[grp][bad] == 0) {
        continue;
      }
      int good = spaces - bad;
      for (int chosen_good = 0; chosen_good <= min(group[grp + 1], good);
           ++chosen_good) {
        for (int chosen_bad = 0;
             chosen_bad <= min(group[grp + 1] - chosen_good, bad);
             ++chosen_bad) {
          int total_chosen = chosen_good + chosen_bad;
          if (1 <= total_chosen && total_chosen <= group[grp + 1]) {
            int new_bad = (bad - chosen_bad) + (group[grp + 1] - total_chosen);
            long long cur_ways = mult(
                mult(ways[grp][bad], C[good][chosen_good]), C[bad][chosen_bad]);
            cur_ways =
                mult(mult(cur_ways, C[group[grp + 1] - 1][total_chosen - 1]),
                     fac[group[grp + 1]]);
            ways[grp + 1][new_bad] += cur_ways;
            ways[grp + 1][new_bad] %= 1000000007LL;
          }
        }
      }
    }
    spaces += group[grp + 1];
  }
  printf("%lld\n", ways[n][0]);
  return 0;
}
int main() {
  int tt = 1;
  for (int t = 1; t <= tt; ++t) {
    solver();
  }
  return 0;
}
