#include <bits/stdc++.h>
using namespace std;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const ll mod = 1e9 + 7;
const int maxn = 303;
ll fac[maxn], ifac[maxn], inv[maxn];
ll nck(ll n, ll k) {
  if (n < k) return 0;
  return fac[n] * ifac[k] % mod * ifac[n - k] % mod;
}
void gen_inv() {
  fac[0] = inv[0] = ifac[0] = 1;
  fac[1] = inv[1] = ifac[1] = 1;
  for (int i = 2; i < maxn; i++) {
    fac[i] = fac[i - 1] * i % mod;
    inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod;
    ifac[i] = ifac[i - 1] * inv[i] % mod;
  }
  assert(nck(4, 2) == 6);
}
void add(ll& x, ll y) {
  if (x >= mod) x %= mod;
  if (y >= mod) y %= mod;
  x += y;
  if (x >= mod) x %= mod;
}
void mul(ll& x, ll y) {
  if (x >= mod) x %= mod;
  if (y >= mod) y %= mod;
  x *= y;
  if (x >= mod) x %= mod;
}
ll dp[maxn][maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  gen_inv();
  map<int, int> groups;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    for (ll j = 2; j * j <= x; j++) {
      if (x % j == 0) {
        while (x % (j * j) == 0) {
          x /= j;
          x /= j;
        }
      }
    }
    groups[x]++;
  }
  n = groups.size();
  vector<int> a;
  for (auto p : groups) {
    a.push_back(p.second);
  }
  dp[0][0] = 1;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    assert(a[i] > 0);
    for (int j = 0; j <= tot + 1; j++) {
      for (int s = 1; s <= min(tot + 1, a[i]); s++) {
        for (int d = 0; d <= min(j, a[i]) && d <= s; d++) {
          ll order = fac[a[i]];
          ll chunks = nck(a[i] - 1, s - 1);
          ll bad = nck(j, d);
          ll place = nck(tot + 1 - j, s - d);
          ll cur = order * chunks % mod * bad % mod * place % mod;
          add(dp[i + 1][j - d + a[i] - s], dp[i][j] * cur);
        }
      }
    }
    tot += a[i];
  }
  ll res = dp[n][0];
  res %= mod;
  res += mod;
  res %= mod;
  out(res);
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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>
using namespace std;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const ll mod = 1e9 + 7;
const int maxn = 303;
ll fac[maxn], ifac[maxn], inv[maxn];
ll nck(ll n, ll k) {
  if (n < k) return 0;
  return fac[n] * ifac[k] % mod * ifac[n - k] % mod;
}
void gen_inv() {
  fac[0] = inv[0] = ifac[0] = 1;
  fac[1] = inv[1] = ifac[1] = 1;
  for (int i = 2; i < maxn; i++) {
    fac[i] = fac[i - 1] * i % mod;
    inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod;
    ifac[i] = ifac[i - 1] * inv[i] % mod;
  }
  assert(nck(4, 2) == 6);
}
void add(ll& x, ll y) {
  if (x >= mod) x %= mod;
  if (y >= mod) y %= mod;
  x += y;
  if (x >= mod) x %= mod;
}
void mul(ll& x, ll y) {
  if (x >= mod) x %= mod;
  if (y >= mod) y %= mod;
  x *= y;
  if (x >= mod) x %= mod;
}
ll dp[maxn][maxn];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  gen_inv();
  map<int, int> groups;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    for (ll j = 2; j * j <= x; j++) {
      if (x % j == 0) {
        while (x % (j * j) == 0) {
          x /= j;
          x /= j;
        }
      }
    }
    groups[x]++;
  }
  n = groups.size();
  vector<int> a;
  for (auto p : groups) {
    a.push_back(p.second);
  }
  dp[0][0] = 1;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    assert(a[i] > 0);
    for (int j = 0; j <= tot + 1; j++) {
      for (int s = 1; s <= min(tot + 1, a[i]); s++) {
        for (int d = 0; d <= min(j, a[i]) && d <= s; d++) {
          ll order = fac[a[i]];
          ll chunks = nck(a[i] - 1, s - 1);
          ll bad = nck(j, d);
          ll place = nck(tot + 1 - j, s - d);
          ll cur = order * chunks % mod * bad % mod * place % mod;
          add(dp[i + 1][j - d + a[i] - s], dp[i][j] * cur);
        }
      }
    }
    tot += a[i];
  }
  ll res = dp[n][0];
  res %= mod;
  res += mod;
  res %= mod;
  out(res);
  return 0;
}

```