#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000000 + 7;
pair<int, int> T[350];
long long fac[350];
long long dp[310][310];
long long newton[310][310];
long long POW[310][310];
long long ne(int n, int k) {
  if (k > n) return 0;
  if (min(n, k) < 0) return 0;
  return newton[n][k];
}
long long magic(vector<int> g) {
  for (int i = 0; i < 310; ++i) newton[i][0] = 1;
  for (int i = 1; i < 310; ++i)
    for (int j = 1; j < 310; ++j) {
      newton[i][j] = (newton[i - 1][j] + newton[i - 1][j - 1]) % mod;
    }
  if (0)
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 10; ++j) printf("%lld ", newton[i][j]);
      puts("");
    }
  dp[0][0] = 1;
  long long S = 0;
  for (int i = 0; i < g.size(); ++i) {
    long long ai = g[i];
    for (int j = 0; j <= S; ++j) {
      dp[i][j] %= mod;
      if (dp[i][j] != 0)
        for (int k = 0; k <= j; ++k)
          for (int l = 0; k + l <= min(S + 1, ai); ++l) {
            if (max(l, k) > 0)
              dp[i + 1][j - k + ai - l - k] += ne(j, k) * ne(1 + S - j, l) %
                                               mod * ne(ai - 1, l + k - 1) %
                                               mod * dp[i][j] % mod;
          }
    }
    S += ai;
  }
  if (0)
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 10; ++j) printf("%lld ", dp[i][j]);
      puts("");
    }
  return dp[g.size()][0] % mod;
}
int main() {
  int n;
  scanf("%d", &n);
  fac[0] = 1;
  for (int i = 1; i < n + 10; ++i) fac[i] = fac[i - 1] * i % mod;
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    for (int j = 31624; j > 0; --j)
      if (x % (j * j) == 0) {
        x /= j * j;
        T[i] = pair<int, int>(x, j);
        break;
      }
  }
  map<int, int> M;
  map<pair<int, int>, int> M2;
  for (int i = 0; i < n; ++i) {
    ++M[T[i].first];
    ++M2[T[i]];
  }
  long long gora = 1;
  long long dol = 1;
  vector<int> groups;
  for (auto it : M) {
    gora = gora * fac[it.second] % mod;
    groups.push_back(it.second);
  }
  for (auto it : M2) dol = dol * fac[it.second] % mod;
  gora = magic(groups) * gora % mod;
  long long exp = mod - 2;
  if (0)
    while (exp) {
      if (exp & 1) gora = gora * dol % mod;
      dol = dol * dol % mod;
      exp /= 2;
    }
  printf("%lld\n", gora);
}

### 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 long long mod = 1000000000 + 7;
pair<int, int> T[350];
long long fac[350];
long long dp[310][310];
long long newton[310][310];
long long POW[310][310];
long long ne(int n, int k) {
  if (k > n) return 0;
  if (min(n, k) < 0) return 0;
  return newton[n][k];
}
long long magic(vector<int> g) {
  for (int i = 0; i < 310; ++i) newton[i][0] = 1;
  for (int i = 1; i < 310; ++i)
    for (int j = 1; j < 310; ++j) {
      newton[i][j] = (newton[i - 1][j] + newton[i - 1][j - 1]) % mod;
    }
  if (0)
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 10; ++j) printf("%lld ", newton[i][j]);
      puts("");
    }
  dp[0][0] = 1;
  long long S = 0;
  for (int i = 0; i < g.size(); ++i) {
    long long ai = g[i];
    for (int j = 0; j <= S; ++j) {
      dp[i][j] %= mod;
      if (dp[i][j] != 0)
        for (int k = 0; k <= j; ++k)
          for (int l = 0; k + l <= min(S + 1, ai); ++l) {
            if (max(l, k) > 0)
              dp[i + 1][j - k + ai - l - k] += ne(j, k) * ne(1 + S - j, l) %
                                               mod * ne(ai - 1, l + k - 1) %
                                               mod * dp[i][j] % mod;
          }
    }
    S += ai;
  }
  if (0)
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 10; ++j) printf("%lld ", dp[i][j]);
      puts("");
    }
  return dp[g.size()][0] % mod;
}
int main() {
  int n;
  scanf("%d", &n);
  fac[0] = 1;
  for (int i = 1; i < n + 10; ++i) fac[i] = fac[i - 1] * i % mod;
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    for (int j = 31624; j > 0; --j)
      if (x % (j * j) == 0) {
        x /= j * j;
        T[i] = pair<int, int>(x, j);
        break;
      }
  }
  map<int, int> M;
  map<pair<int, int>, int> M2;
  for (int i = 0; i < n; ++i) {
    ++M[T[i].first];
    ++M2[T[i]];
  }
  long long gora = 1;
  long long dol = 1;
  vector<int> groups;
  for (auto it : M) {
    gora = gora * fac[it.second] % mod;
    groups.push_back(it.second);
  }
  for (auto it : M2) dol = dol * fac[it.second] % mod;
  gora = magic(groups) * gora % mod;
  long long exp = mod - 2;
  if (0)
    while (exp) {
      if (exp & 1) gora = gora * dol % mod;
      dol = dol * dol % mod;
      exp /= 2;
    }
  printf("%lld\n", gora);
}

```