#include <bits/stdc++.h>
using namespace std;
bool issq(long long x) {
  long long y = sqrtl(x);
  y -= 2;
  y = max(y, 1LL);
  for (int i = 0; i < 4; i++) {
    if ((y + i) * (y + i) == x) return true;
  }
  return false;
}
long long modexp(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if ((b & 1)) {
      ans *= a;
      ans %= 1000000007;
    }
    a *= a;
    a %= 1000000007;
    b >>= 1;
  }
  return ans;
}
void mult(long long *ans, long long by) {
  (*ans) *= by;
  (*ans) %= 1000000007;
}
void div(long long *ans, long long by) {
  (*ans) *= modexp(by, 1000000007 - 2);
  (*ans) %= 1000000007;
}
long long nCr[1000][1000];
vector<int> compsz;
vector<int> pre;
long long dp[301][301];
long long getans(int pos, int num_edges) {
  if (pos == 1) {
    return num_edges + 1 == compsz[pos] ? 1 : 0;
  }
  long long &ans = dp[pos][num_edges];
  if (ans != -1) return ans;
  ans = 0;
  for (int prv = 0; prv < pre[pos - 1]; prv++) {
    int y = pre[pos - 1] - prv + 1;
    if (y < 0) break;
    long long all = getans(pos - 1, prv);
    for (int br = 0; br <= prv; br++) {
      int edges_to_add = num_edges - (prv - br);
      int num_non_edges = compsz[pos] - edges_to_add - br;
      int use = num_non_edges + br;
      if (edges_to_add < 0 || num_non_edges < 0 || use < 0) {
        continue;
      }
      long long cans = 1;
      mult(&cans, nCr[prv][br]);
      mult(&cans, nCr[y][num_non_edges]);
      if (use == 0) {
        if (edges_to_add != 0) {
          cans = 0;
        }
      } else {
        mult(&cans, nCr[edges_to_add + use - 1][use - 1]);
      }
      mult(&cans, all);
      ans += cans;
      ans %= 1000000007;
    }
  }
  return ans;
}
long long fact[1000];
int main() {
  int n;
  memset(dp, -1, sizeof(dp));
  scanf("%d", &n);
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%Ld", &a[i]);
  }
  vector<int> used(n, 0);
  nCr[0][0] = 1;
  fact[0] = 1;
  for (int i = 1; i < 1000; i++) {
    nCr[i][0] = 1;
    fact[i] = (fact[i - 1] * i) % 1000000007;
    for (int j = 1; j <= i; j++) {
      nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % 1000000007;
    }
  }
  long long ans = 1;
  compsz.push_back(0);
  for (int i = 0; i < n; i++) {
    map<int, int> ccomp;
    int sz = 0;
    if (used[i]) continue;
    for (int j = i; j < n; j++) {
      if (issq(a[i] * a[j])) {
        ccomp[a[j]]++;
        sz++;
        used[j] = 1;
      }
    }
    compsz.push_back(sz);
    mult(&ans, fact[sz]);
    for (const auto &it : ccomp) {
    }
  }
  pre.resize(n + 1);
  for (int i = 1; i < (int)compsz.size(); i++) {
    pre[i] = pre[i - 1];
    pre[i] += compsz[i];
  }
  mult(&ans, getans((int)compsz.size() - 1, 0));
  cout << ans << endl;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
bool issq(long long x) {
  long long y = sqrtl(x);
  y -= 2;
  y = max(y, 1LL);
  for (int i = 0; i < 4; i++) {
    if ((y + i) * (y + i) == x) return true;
  }
  return false;
}
long long modexp(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if ((b & 1)) {
      ans *= a;
      ans %= 1000000007;
    }
    a *= a;
    a %= 1000000007;
    b >>= 1;
  }
  return ans;
}
void mult(long long *ans, long long by) {
  (*ans) *= by;
  (*ans) %= 1000000007;
}
void div(long long *ans, long long by) {
  (*ans) *= modexp(by, 1000000007 - 2);
  (*ans) %= 1000000007;
}
long long nCr[1000][1000];
vector<int> compsz;
vector<int> pre;
long long dp[301][301];
long long getans(int pos, int num_edges) {
  if (pos == 1) {
    return num_edges + 1 == compsz[pos] ? 1 : 0;
  }
  long long &ans = dp[pos][num_edges];
  if (ans != -1) return ans;
  ans = 0;
  for (int prv = 0; prv < pre[pos - 1]; prv++) {
    int y = pre[pos - 1] - prv + 1;
    if (y < 0) break;
    long long all = getans(pos - 1, prv);
    for (int br = 0; br <= prv; br++) {
      int edges_to_add = num_edges - (prv - br);
      int num_non_edges = compsz[pos] - edges_to_add - br;
      int use = num_non_edges + br;
      if (edges_to_add < 0 || num_non_edges < 0 || use < 0) {
        continue;
      }
      long long cans = 1;
      mult(&cans, nCr[prv][br]);
      mult(&cans, nCr[y][num_non_edges]);
      if (use == 0) {
        if (edges_to_add != 0) {
          cans = 0;
        }
      } else {
        mult(&cans, nCr[edges_to_add + use - 1][use - 1]);
      }
      mult(&cans, all);
      ans += cans;
      ans %= 1000000007;
    }
  }
  return ans;
}
long long fact[1000];
int main() {
  int n;
  memset(dp, -1, sizeof(dp));
  scanf("%d", &n);
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%Ld", &a[i]);
  }
  vector<int> used(n, 0);
  nCr[0][0] = 1;
  fact[0] = 1;
  for (int i = 1; i < 1000; i++) {
    nCr[i][0] = 1;
    fact[i] = (fact[i - 1] * i) % 1000000007;
    for (int j = 1; j <= i; j++) {
      nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % 1000000007;
    }
  }
  long long ans = 1;
  compsz.push_back(0);
  for (int i = 0; i < n; i++) {
    map<int, int> ccomp;
    int sz = 0;
    if (used[i]) continue;
    for (int j = i; j < n; j++) {
      if (issq(a[i] * a[j])) {
        ccomp[a[j]]++;
        sz++;
        used[j] = 1;
      }
    }
    compsz.push_back(sz);
    mult(&ans, fact[sz]);
    for (const auto &it : ccomp) {
    }
  }
  pre.resize(n + 1);
  for (int i = 1; i < (int)compsz.size(); i++) {
    pre[i] = pre[i - 1];
    pre[i] += compsz[i];
  }
  mult(&ans, getans((int)compsz.size() - 1, 0));
  cout << ans << endl;
  return 0;
}

```