#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd;
const long long maxn = 3e2 + 10;
const long long mod = 1e9 + 7;
const long long base = 3e18;
long long a[maxn];
long long dp[maxn][maxn];
long long par[maxn];
long long find_par(long long u) {
  if (par[u] < 0) return u;
  return par[u] = find_par(par[u]);
}
void dsu(long long x, long long y) {
  x = find_par(x);
  y = find_par(y);
  if (x == y) return;
  if (par[x] > par[y]) swap(x, y);
  par[x] += par[y];
  par[y] = x;
}
long long gt[maxn];
long long gtv[maxn];
long long mu(long long a, long long n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  long long t = mu(a, n / 2);
  if (n % 2 == 0) return (t * t) % mod;
  return ((t * t) % mod * a) % mod;
}
void setup() {
  gt[0] = 1;
  for (int i = 1; i < maxn; i++) {
    gt[i] = (gt[i - 1] * i) % mod;
  }
  gtv[maxn - 1] = mu(gt[maxn - 1], mod - 2);
  for (int i = maxn - 2; i >= 0; i--) {
    gtv[i] = (gtv[i + 1] * (i + 1)) % mod;
  }
}
long long nck(long long n, long long k) {
  if (n < k) return 0;
  return ((gt[n] * gtv[k]) % mod * gtv[n - k]) % mod;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  if (fopen("t.inp", "r")) {
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
  }
  setup();
  long long n;
  cin >> n;
  dp[0][0] = 1;
  memset(par, -1, sizeof(par));
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      long long h = a[i] * a[j];
      long long t = sqrt(h);
      if (t * t == h) dsu(i, j);
    }
  }
  vector<long long> vt;
  for (int i = 1; i <= n; i++) {
    if (find_par(i) == i) {
      vt.push_back(-par[i]);
    }
  }
  long long pre = 0;
  for (int j = 1; j <= vt.size(); j++) {
    long long siz = vt[j - 1];
    for (int i = 1; i <= siz; i++) {
      long long pls = siz - i;
      long long nw = (nck(siz - 1, i - 1) * gt[siz]) % mod;
      for (int wr_p = 0; wr_p <= max(pre - 1, 0ll); wr_p++) {
        for (int nwr_p = 0; nwr_p <= min(i, wr_p); nwr_p++) {
          long long res_node = i - nwr_p;
          long long num_remain_slot = pre + 1 - wr_p;
          if (!dp[j - 1][wr_p]) continue;
          dp[j][wr_p - nwr_p + pls] =
              (dp[j][wr_p - nwr_p + pls] +
               (((dp[j - 1][wr_p] * nw) % mod * nck(wr_p, nwr_p)) % mod *
                nck(num_remain_slot, res_node)) %
                   mod) %
              mod;
        }
      }
    }
    pre += siz;
  }
  cout << dp[vt.size()][0] << "\n";
}

### Prompt

Create a solution in cpp for 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;
mt19937_64 rnd;
const long long maxn = 3e2 + 10;
const long long mod = 1e9 + 7;
const long long base = 3e18;
long long a[maxn];
long long dp[maxn][maxn];
long long par[maxn];
long long find_par(long long u) {
  if (par[u] < 0) return u;
  return par[u] = find_par(par[u]);
}
void dsu(long long x, long long y) {
  x = find_par(x);
  y = find_par(y);
  if (x == y) return;
  if (par[x] > par[y]) swap(x, y);
  par[x] += par[y];
  par[y] = x;
}
long long gt[maxn];
long long gtv[maxn];
long long mu(long long a, long long n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  long long t = mu(a, n / 2);
  if (n % 2 == 0) return (t * t) % mod;
  return ((t * t) % mod * a) % mod;
}
void setup() {
  gt[0] = 1;
  for (int i = 1; i < maxn; i++) {
    gt[i] = (gt[i - 1] * i) % mod;
  }
  gtv[maxn - 1] = mu(gt[maxn - 1], mod - 2);
  for (int i = maxn - 2; i >= 0; i--) {
    gtv[i] = (gtv[i + 1] * (i + 1)) % mod;
  }
}
long long nck(long long n, long long k) {
  if (n < k) return 0;
  return ((gt[n] * gtv[k]) % mod * gtv[n - k]) % mod;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  if (fopen("t.inp", "r")) {
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
  }
  setup();
  long long n;
  cin >> n;
  dp[0][0] = 1;
  memset(par, -1, sizeof(par));
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      long long h = a[i] * a[j];
      long long t = sqrt(h);
      if (t * t == h) dsu(i, j);
    }
  }
  vector<long long> vt;
  for (int i = 1; i <= n; i++) {
    if (find_par(i) == i) {
      vt.push_back(-par[i]);
    }
  }
  long long pre = 0;
  for (int j = 1; j <= vt.size(); j++) {
    long long siz = vt[j - 1];
    for (int i = 1; i <= siz; i++) {
      long long pls = siz - i;
      long long nw = (nck(siz - 1, i - 1) * gt[siz]) % mod;
      for (int wr_p = 0; wr_p <= max(pre - 1, 0ll); wr_p++) {
        for (int nwr_p = 0; nwr_p <= min(i, wr_p); nwr_p++) {
          long long res_node = i - nwr_p;
          long long num_remain_slot = pre + 1 - wr_p;
          if (!dp[j - 1][wr_p]) continue;
          dp[j][wr_p - nwr_p + pls] =
              (dp[j][wr_p - nwr_p + pls] +
               (((dp[j - 1][wr_p] * nw) % mod * nck(wr_p, nwr_p)) % mod *
                nck(num_remain_slot, res_node)) %
                   mod) %
              mod;
        }
      }
    }
    pre += siz;
  }
  cout << dp[vt.size()][0] << "\n";
}

```