#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int mod = 1e9 + 7;
long long a[maxn], par[maxn];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
int chk(long long x) {
  long long p = sqrt(x) - 3;
  for (long long i = p; i <= p + 6; ++i)
    if (i * i == x) return 1;
  return 0;
}
long long sz[maxn];
long long comb[405][405];
void init() {
  for (int i = 0; i <= 400; ++i) comb[i][0] = 1;
  for (int i = 1; i <= 400; ++i)
    for (int j = 1; j <= 400; ++j) {
      comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
      if (comb[i][j] > mod) comb[i][j] -= mod;
    }
}
long long dp[405][405];
long long b[405], tp = 0;
long long f[405];
int main() {
  init();
  f[0] = 1;
  for (int i = 1; i <= 400; ++i) f[i] = i * f[i - 1] % mod;
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) par[i] = i;
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (chk(a[i] * a[j])) par[find(j)] = find(i);
  int tp = 0;
  for (int i = 1; i <= n; ++i) sz[find(i)]++;
  for (int i = 1; i <= n; ++i)
    if (sz[i]) b[++tp] = sz[i];
  long long cur = b[1];
  dp[1][b[1] - 1] = 1;
  for (int i = 2; i <= tp; ++i) {
    for (int j = 0; j < cur; ++j)
      for (int k = 1; k <= b[i]; ++k)
        for (int p = 0; p <= min(j, k); ++p) {
          dp[i][j - p + b[i] - k] += dp[i - 1][j] * comb[j][p] % mod *
                                     comb[cur + 1 - j][k - p] % mod *
                                     comb[b[i] - 1][k - 1] % mod;
          dp[i][j - p + b[i] - k] %= mod;
        }
    cur += b[i];
  }
  long long ans = dp[tp][0];
  for (int i = 1; i <= tp; ++i) ans = ans * f[b[i]] % mod;
  cout << ans << '\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;
const int maxn = 405;
const int mod = 1e9 + 7;
long long a[maxn], par[maxn];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
int chk(long long x) {
  long long p = sqrt(x) - 3;
  for (long long i = p; i <= p + 6; ++i)
    if (i * i == x) return 1;
  return 0;
}
long long sz[maxn];
long long comb[405][405];
void init() {
  for (int i = 0; i <= 400; ++i) comb[i][0] = 1;
  for (int i = 1; i <= 400; ++i)
    for (int j = 1; j <= 400; ++j) {
      comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
      if (comb[i][j] > mod) comb[i][j] -= mod;
    }
}
long long dp[405][405];
long long b[405], tp = 0;
long long f[405];
int main() {
  init();
  f[0] = 1;
  for (int i = 1; i <= 400; ++i) f[i] = i * f[i - 1] % mod;
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) par[i] = i;
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (chk(a[i] * a[j])) par[find(j)] = find(i);
  int tp = 0;
  for (int i = 1; i <= n; ++i) sz[find(i)]++;
  for (int i = 1; i <= n; ++i)
    if (sz[i]) b[++tp] = sz[i];
  long long cur = b[1];
  dp[1][b[1] - 1] = 1;
  for (int i = 2; i <= tp; ++i) {
    for (int j = 0; j < cur; ++j)
      for (int k = 1; k <= b[i]; ++k)
        for (int p = 0; p <= min(j, k); ++p) {
          dp[i][j - p + b[i] - k] += dp[i - 1][j] * comb[j][p] % mod *
                                     comb[cur + 1 - j][k - p] % mod *
                                     comb[b[i] - 1][k - 1] % mod;
          dp[i][j - p + b[i] - k] %= mod;
        }
    cur += b[i];
  }
  long long ans = dp[tp][0];
  for (int i = 1; i <= tp; ++i) ans = ans * f[b[i]] % mod;
  cout << ans << '\n';
}

```