#include <bits/stdc++.h>
namespace IO {
const int N = 1e6;
static char s[N], *S = s, *T = s, t[N], *E = t;
inline void flush() { fwrite(t, 1, E - t, stdout), E = t; }
inline char getc() {
  if (S == T) T = (S = s) + fread(s, 1, N, stdin);
  return S == T ? 0 : *S++;
}
inline void putc(char c) {
  if (E == t + N - 1) flush();
  *E++ = c;
}
}  // namespace IO
using IO::flush;
using IO::getc;
using IO::putc;
using namespace std;
using ll = long long;
using PII = pair<int, int>;
template <class T>
inline T read() {
  T ___ = 1, __ = getc(), _ = 0;
  for (; !isdigit(__); __ = getc())
    if (__ == '-') ___ = -1;
  for (; isdigit(__); __ = getc()) _ = _ * 10 + __ - 48;
  return _ * ___;
}
template <class T>
inline void write(T _, char __ = '\n') {
  if (!_) putc(48);
  if (_ < 0) putc('-'), _ = -_;
  static int sta[111], tp;
  for (sta[tp = 0] = __; _; _ /= 10) sta[++tp] = _ % 10 + 48;
  while (~tp) putc(sta[tp--]);
}
template <class T>
inline bool chkmax(T &_, T __) {
  return _ < __ ? _ = __, 1 : 0;
}
template <class T>
inline bool chkmin(T &_, T __) {
  return _ > __ ? _ = __, 1 : 0;
}
inline void proStatus() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>());
}
const int N = 300;
const int mod = 1e9 + 7;
int qpow(int a, int first) {
  int ret = 1;
  while (first) {
    if (first & 1) ret = 1ll * ret * a % mod;
    first >>= 1, a = 1ll * a * a % mod;
  }
  return ret;
}
int s[N + 5];
int a[N + 5], n;
int b[N + 5], m;
int dp[N + 5][N + 5];
int fac[N + 5], ifac[N + 5];
int C(int first, int second) {
  if (first < second) return 0;
  return fac[first] * (ll)ifac[second] % mod * ifac[first - second] % mod;
}
signed main() {
  n = read<int>();
  fac[0] = ifac[0] = 1;
  for (int i = (1), iend = (n); i <= iend; ++i) {
    a[i] = read<int>();
    for (int first = 2; first * first <= a[i]; ++first)
      while (a[i] % (first * first) == 0) a[i] /= first * first;
    fac[i] = fac[i - 1] * (ll)i % mod;
  }
  ifac[n] = qpow(fac[n], mod - 2);
  for (int i = (n), iend = (1); i >= iend; --i)
    ifac[i - 1] = ifac[i] * (ll)i % mod;
  sort(a + 1, a + n + 1);
  for (int i = (1), iend = (n); i <= iend; ++i) {
    int j = i;
    while (j < n && a[j + 1] == a[i]) ++j;
    b[++m] = j - i + 1, i = j;
    s[m] = s[m - 1] + b[m];
  }
  dp[0][0] = 1;
  for (int i = 0, iend = (m); i < iend; ++i)
    for (int j = (0), jend = (s[i]); j <= jend; ++j)
      if (dp[i][j])
        for (int k = (1), kend = (b[i + 1]); k <= kend; ++k)
          for (int t = (0), tend = (min(k, j)); t <= tend; ++t) {
            (dp[i + 1][j + b[i + 1] - k - t] +=
             1ll * fac[b[i + 1]] * dp[i][j] % mod * C(b[i + 1] - 1, k - 1) %
             mod * C(j, t) % mod * C(s[i] - j + 1, k - t) % mod) %= mod;
          }
  printf("%d\n", dp[m][0]);
  return flush(), 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

A year ago on the bench in public park Leha found an array of n numbers. Leha believes that permutation p is right if for all 1 ≤ i < n condition, that api·api + 1 is not perfect square, holds. Leha wants to find number of right permutations modulo 109 + 7.

Input

First line of input data contains single integer n (1 ≤ n ≤ 300) — length of the array.

Next line contains n integers a1, a2, ... , an (1 ≤ ai ≤ 109) — found array.

Output

Output single integer — number of right permutations modulo 109 + 7.

Examples

Input

3
1 2 4


Output

2


Input

7
5 2 4 2 4 1 1


Output

144

Note

For first example:

[1, 2, 4] — right permutation, because 2 and 8 are not perfect squares.

[1, 4, 2] — wrong permutation, because 4 is square of 2.

[2, 1, 4] — wrong permutation, because 4 is square of 2.

[2, 4, 1] — wrong permutation, because 4 is square of 2.

[4, 1, 2] — wrong permutation, because 4 is square of 2.

[4, 2, 1] — right permutation, because 8 and 2 are not perfect squares.

### Response

```cpp
#include <bits/stdc++.h>
namespace IO {
const int N = 1e6;
static char s[N], *S = s, *T = s, t[N], *E = t;
inline void flush() { fwrite(t, 1, E - t, stdout), E = t; }
inline char getc() {
  if (S == T) T = (S = s) + fread(s, 1, N, stdin);
  return S == T ? 0 : *S++;
}
inline void putc(char c) {
  if (E == t + N - 1) flush();
  *E++ = c;
}
}  // namespace IO
using IO::flush;
using IO::getc;
using IO::putc;
using namespace std;
using ll = long long;
using PII = pair<int, int>;
template <class T>
inline T read() {
  T ___ = 1, __ = getc(), _ = 0;
  for (; !isdigit(__); __ = getc())
    if (__ == '-') ___ = -1;
  for (; isdigit(__); __ = getc()) _ = _ * 10 + __ - 48;
  return _ * ___;
}
template <class T>
inline void write(T _, char __ = '\n') {
  if (!_) putc(48);
  if (_ < 0) putc('-'), _ = -_;
  static int sta[111], tp;
  for (sta[tp = 0] = __; _; _ /= 10) sta[++tp] = _ % 10 + 48;
  while (~tp) putc(sta[tp--]);
}
template <class T>
inline bool chkmax(T &_, T __) {
  return _ < __ ? _ = __, 1 : 0;
}
template <class T>
inline bool chkmin(T &_, T __) {
  return _ > __ ? _ = __, 1 : 0;
}
inline void proStatus() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>());
}
const int N = 300;
const int mod = 1e9 + 7;
int qpow(int a, int first) {
  int ret = 1;
  while (first) {
    if (first & 1) ret = 1ll * ret * a % mod;
    first >>= 1, a = 1ll * a * a % mod;
  }
  return ret;
}
int s[N + 5];
int a[N + 5], n;
int b[N + 5], m;
int dp[N + 5][N + 5];
int fac[N + 5], ifac[N + 5];
int C(int first, int second) {
  if (first < second) return 0;
  return fac[first] * (ll)ifac[second] % mod * ifac[first - second] % mod;
}
signed main() {
  n = read<int>();
  fac[0] = ifac[0] = 1;
  for (int i = (1), iend = (n); i <= iend; ++i) {
    a[i] = read<int>();
    for (int first = 2; first * first <= a[i]; ++first)
      while (a[i] % (first * first) == 0) a[i] /= first * first;
    fac[i] = fac[i - 1] * (ll)i % mod;
  }
  ifac[n] = qpow(fac[n], mod - 2);
  for (int i = (n), iend = (1); i >= iend; --i)
    ifac[i - 1] = ifac[i] * (ll)i % mod;
  sort(a + 1, a + n + 1);
  for (int i = (1), iend = (n); i <= iend; ++i) {
    int j = i;
    while (j < n && a[j + 1] == a[i]) ++j;
    b[++m] = j - i + 1, i = j;
    s[m] = s[m - 1] + b[m];
  }
  dp[0][0] = 1;
  for (int i = 0, iend = (m); i < iend; ++i)
    for (int j = (0), jend = (s[i]); j <= jend; ++j)
      if (dp[i][j])
        for (int k = (1), kend = (b[i + 1]); k <= kend; ++k)
          for (int t = (0), tend = (min(k, j)); t <= tend; ++t) {
            (dp[i + 1][j + b[i + 1] - k - t] +=
             1ll * fac[b[i + 1]] * dp[i][j] % mod * C(b[i + 1] - 1, k - 1) %
             mod * C(j, t) % mod * C(s[i] - j + 1, k - t) % mod) %= mod;
          }
  printf("%d\n", dp[m][0]);
  return flush(), 0;
}

```