#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0;
const long long maxn = 400, mod = 1e9 + 7;
long long ans = 1;
map<int, int> m;
int t = 0;
long long c[2 * maxn][2 * maxn], f[maxn][maxn];
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    for (long long j = 2; j <= sqrt(x) + 1; j++)
      while (x % (j * j) == 0) x /= j * j;
    m[x]++;
  }
  for (int i = 0; i <= 2 * n; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  f[0][0] = 1;
  t = 0, cnt = 0;
  for (auto x : m) {
    int sz = x.second;
    for (int i = 1; i <= sz; i++) ans = (ans * i) % mod;
    for (int i = 0; i <= t; i++)
      if (f[cnt][i]) {
        for (int j = 1; j <= sz; j++) {
          for (int k = 0; k <= j && k <= i; k++) {
            long long &dp = f[cnt + 1][i - k + sz - j];
            dp = (dp + f[cnt][i] * c[i][k] % mod * c[sz - 1][j - 1] % mod *
                           c[t + 1 - i][j - k] % mod) %
                 mod;
          }
        }
      }
    cnt++;
    t += sz;
  }
  cout << ans * f[cnt][0] % mod;
  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;
int n, cnt = 0;
const long long maxn = 400, mod = 1e9 + 7;
long long ans = 1;
map<int, int> m;
int t = 0;
long long c[2 * maxn][2 * maxn], f[maxn][maxn];
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    for (long long j = 2; j <= sqrt(x) + 1; j++)
      while (x % (j * j) == 0) x /= j * j;
    m[x]++;
  }
  for (int i = 0; i <= 2 * n; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  f[0][0] = 1;
  t = 0, cnt = 0;
  for (auto x : m) {
    int sz = x.second;
    for (int i = 1; i <= sz; i++) ans = (ans * i) % mod;
    for (int i = 0; i <= t; i++)
      if (f[cnt][i]) {
        for (int j = 1; j <= sz; j++) {
          for (int k = 0; k <= j && k <= i; k++) {
            long long &dp = f[cnt + 1][i - k + sz - j];
            dp = (dp + f[cnt][i] * c[i][k] % mod * c[sz - 1][j - 1] % mod *
                           c[t + 1 - i][j - k] % mod) %
                 mod;
          }
        }
      }
    cnt++;
    t += sz;
  }
  cout << ans * f[cnt][0] % mod;
  return 0;
}

```