#include <bits/stdc++.h>
using namespace std;
const int maxN = 300 + 190;
const long long mod = 1e9 + 7;
int n, N;
long long arr[maxN], num[maxN], g[maxN], c[maxN][maxN], p[maxN], f[maxN][maxN];
void io() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
}
bool check(long long a, long long b) {
  long long tmp = sqrt(a * b);
  return (a * b == tmp * tmp);
}
long long C(int k, int n1) {
  if (k > n1) return 0;
  if (2 * k >= n1) k = n1 - k;
  if (c[k][n1]) return c[k][n1];
  if (k == 0) return 1;
  return (c[k][n1] = (C(k, n1 - 1) + C(k - 1, n1 - 1)) % mod);
}
int main() {
  io();
  cin >> n;
  N = 0;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  for (int i = 1; i <= n; ++i) {
    if (!g[i]) {
      g[i] = ++N;
      num[g[i]] = 1;
      for (int j = i + 1; j <= n; ++j)
        if (check(arr[i], arr[j])) g[j] = g[i], num[g[i]]++;
    }
  }
  p[1] = 1;
  for (int i = 2; i <= n; ++i) p[i] = (p[i - 1] * i) % mod;
  f[0][0] = 1;
  f[1][num[g[1]] - 1] = p[num[g[1]]];
  long long total = 0;
  long long sz = 0;
  for (int i = 1; i < N; ++i) {
    total += num[i];
    sz = num[i + 1];
    for (int j = 0; j < total; ++j) {
      if (!f[i][j]) continue;
      for (int s = 1; s <= min(sz, total + 1); ++s) {
        for (int d = 0; d <= min(j, s); ++d) {
          f[i + 1][j + sz - s - d] += f[i][j] * p[sz] % mod * C(s - 1, sz - 1) %
                                      mod * C(d, j) % mod *
                                      C(s - d, total + 1 - j) % mod;
          f[i + 1][j + sz - s - d] %= mod;
        }
      }
    }
  }
  cout << f[N][0] << '\n';
  return 0;
}

### Prompt

Please formulate 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;
const int maxN = 300 + 190;
const long long mod = 1e9 + 7;
int n, N;
long long arr[maxN], num[maxN], g[maxN], c[maxN][maxN], p[maxN], f[maxN][maxN];
void io() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
}
bool check(long long a, long long b) {
  long long tmp = sqrt(a * b);
  return (a * b == tmp * tmp);
}
long long C(int k, int n1) {
  if (k > n1) return 0;
  if (2 * k >= n1) k = n1 - k;
  if (c[k][n1]) return c[k][n1];
  if (k == 0) return 1;
  return (c[k][n1] = (C(k, n1 - 1) + C(k - 1, n1 - 1)) % mod);
}
int main() {
  io();
  cin >> n;
  N = 0;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  for (int i = 1; i <= n; ++i) {
    if (!g[i]) {
      g[i] = ++N;
      num[g[i]] = 1;
      for (int j = i + 1; j <= n; ++j)
        if (check(arr[i], arr[j])) g[j] = g[i], num[g[i]]++;
    }
  }
  p[1] = 1;
  for (int i = 2; i <= n; ++i) p[i] = (p[i - 1] * i) % mod;
  f[0][0] = 1;
  f[1][num[g[1]] - 1] = p[num[g[1]]];
  long long total = 0;
  long long sz = 0;
  for (int i = 1; i < N; ++i) {
    total += num[i];
    sz = num[i + 1];
    for (int j = 0; j < total; ++j) {
      if (!f[i][j]) continue;
      for (int s = 1; s <= min(sz, total + 1); ++s) {
        for (int d = 0; d <= min(j, s); ++d) {
          f[i + 1][j + sz - s - d] += f[i][j] * p[sz] % mod * C(s - 1, sz - 1) %
                                      mod * C(d, j) % mod *
                                      C(s - d, total + 1 - j) % mod;
          f[i + 1][j + sz - s - d] %= mod;
        }
      }
    }
  }
  cout << f[N][0] << '\n';
  return 0;
}

```