#include <bits/stdc++.h>
using namespace std;
const int N = 610;
int f[N][N];
int C[N][N];
int main() {
  int i, j, n, x, t, k, m, pi = 1;
  scanf("%d", &n);
  map<int, int> mp;
  map<int, int>::iterator it;
  for (i = 1; i <= n; ++i) {
    scanf("%d", &x);
    for (k = 2; k * k <= x; ++k) {
      while (!(x % (k * k))) {
        x /= k * k;
      }
    }
    ++mp[x];
  }
  const int mod = 1e9 + 7;
  for (i = 0; i <= n * 2; ++i) {
    for (j = C[i][0] = 1; j <= i; ++j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
  f[0][0] = 1;
  n = m = 0;
  for (it = mp.begin(); it != mp.end(); ++it, ++n, m += t) {
    t = it->second;
    for (i = 1; i <= t; ++i) {
      pi = 1LL * pi * i % mod;
    }
    for (i = 0; i <= m; ++i) {
      if (f[n][i]) {
        for (k = 1; k <= t; ++k) {
          for (j = 0; j <= i && j <= k; ++j) {
            f[n + 1][i - j + t - k] =
                (f[n + 1][i - j + t - k] + 1LL * f[n][i] * C[t - 1][k - 1] %
                                               mod * C[i][j] % mod *
                                               C[m + 1 - i][k - j] % mod) %
                mod;
          }
        }
      }
    }
  }
  printf("%d\n", int(1LL * f[n][0] * pi % mod));
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 N = 610;
int f[N][N];
int C[N][N];
int main() {
  int i, j, n, x, t, k, m, pi = 1;
  scanf("%d", &n);
  map<int, int> mp;
  map<int, int>::iterator it;
  for (i = 1; i <= n; ++i) {
    scanf("%d", &x);
    for (k = 2; k * k <= x; ++k) {
      while (!(x % (k * k))) {
        x /= k * k;
      }
    }
    ++mp[x];
  }
  const int mod = 1e9 + 7;
  for (i = 0; i <= n * 2; ++i) {
    for (j = C[i][0] = 1; j <= i; ++j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
  f[0][0] = 1;
  n = m = 0;
  for (it = mp.begin(); it != mp.end(); ++it, ++n, m += t) {
    t = it->second;
    for (i = 1; i <= t; ++i) {
      pi = 1LL * pi * i % mod;
    }
    for (i = 0; i <= m; ++i) {
      if (f[n][i]) {
        for (k = 1; k <= t; ++k) {
          for (j = 0; j <= i && j <= k; ++j) {
            f[n + 1][i - j + t - k] =
                (f[n + 1][i - j + t - k] + 1LL * f[n][i] * C[t - 1][k - 1] %
                                               mod * C[i][j] % mod *
                                               C[m + 1 - i][k - j] % mod) %
                mod;
          }
        }
      }
    }
  }
  printf("%d\n", int(1LL * f[n][0] * pi % mod));
  return 0;
}

```