#include <bits/stdc++.h>
using namespace std;
const double eps = 0.000000000000001;
int n, A[310];
int corr(int &x) {
  int i, y = 1;
  for (i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int c = 0;
      while (x % i == 0) {
        c ^= 1;
        x /= i;
      }
      if (c > 0) {
        y *= i;
      }
    }
  }
  if (x > 1) {
    y *= x;
  }
  return x = y;
}
int p = -1;
int siz[310], fac[310], tot[310];
long long dp[310][310], ncr[410][410];
void prencr() {
  int i, j;
  for (i = 0; i <= 400; i++) {
    for (j = 0; j <= i; j++) {
      if (j == 0)
        ncr[i][j] = 1;
      else if (i == j)
        ncr[i][j] = 1;
      else
        ncr[i][j] = (ncr[i - 1][j - 1] + ncr[i - 1][j]) % 1000000007;
    }
  }
}
int main() {
  prencr();
  scanf("%d", &n);
  int i, j;
  for (i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    corr(A[i]);
  }
  sort(A, A + n);
  fac[0] = 1;
  int lst = -1;
  for (i = 0; i < n; i++) {
    if (A[i] == lst) {
      siz[p]++;
    } else {
      lst = A[i];
      p++;
      siz[p] = 1;
    }
    fac[i + 1] = (1LL * (i + 1) * fac[i]) % 1000000007;
  }
  p++;
  tot[0] = siz[0];
  for (i = 1; i < p; i++) {
    tot[i] = siz[i] + tot[i - 1];
  }
  dp[0][siz[0] - 1] = 1;
  for (i = 1; i < p; i++) {
    for (j = 0; j < n; j++) {
      if (dp[i - 1][j] == 0) {
        continue;
      }
      int k, placed = tot[i - 1], limp = min(siz[i], placed + 1);
      for (int slots = 1; slots <= limp; slots++) {
        for (int rejc = 0; rejc <= min(j, slots); rejc++) {
          dp[i][j + siz[i] - slots - rejc] +=
              (((((1LL * dp[i - 1][j] * ncr[siz[i] - 1][slots - 1]) %
                  1000000007) *
                 ncr[j][rejc]) %
                1000000007) *
               ncr[placed + 1 - j][slots - rejc]) %
              1000000007;
          dp[i][j + siz[i] - slots - rejc] %= 1000000007;
        }
      }
    }
  }
  long long ans = dp[p - 1][0];
  for (i = 0; i < p; i++) {
    ans = (ans * fac[siz[i]]) % 1000000007;
  }
  printf("%lld\n", ans);
  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;
const double eps = 0.000000000000001;
int n, A[310];
int corr(int &x) {
  int i, y = 1;
  for (i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int c = 0;
      while (x % i == 0) {
        c ^= 1;
        x /= i;
      }
      if (c > 0) {
        y *= i;
      }
    }
  }
  if (x > 1) {
    y *= x;
  }
  return x = y;
}
int p = -1;
int siz[310], fac[310], tot[310];
long long dp[310][310], ncr[410][410];
void prencr() {
  int i, j;
  for (i = 0; i <= 400; i++) {
    for (j = 0; j <= i; j++) {
      if (j == 0)
        ncr[i][j] = 1;
      else if (i == j)
        ncr[i][j] = 1;
      else
        ncr[i][j] = (ncr[i - 1][j - 1] + ncr[i - 1][j]) % 1000000007;
    }
  }
}
int main() {
  prencr();
  scanf("%d", &n);
  int i, j;
  for (i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    corr(A[i]);
  }
  sort(A, A + n);
  fac[0] = 1;
  int lst = -1;
  for (i = 0; i < n; i++) {
    if (A[i] == lst) {
      siz[p]++;
    } else {
      lst = A[i];
      p++;
      siz[p] = 1;
    }
    fac[i + 1] = (1LL * (i + 1) * fac[i]) % 1000000007;
  }
  p++;
  tot[0] = siz[0];
  for (i = 1; i < p; i++) {
    tot[i] = siz[i] + tot[i - 1];
  }
  dp[0][siz[0] - 1] = 1;
  for (i = 1; i < p; i++) {
    for (j = 0; j < n; j++) {
      if (dp[i - 1][j] == 0) {
        continue;
      }
      int k, placed = tot[i - 1], limp = min(siz[i], placed + 1);
      for (int slots = 1; slots <= limp; slots++) {
        for (int rejc = 0; rejc <= min(j, slots); rejc++) {
          dp[i][j + siz[i] - slots - rejc] +=
              (((((1LL * dp[i - 1][j] * ncr[siz[i] - 1][slots - 1]) %
                  1000000007) *
                 ncr[j][rejc]) %
                1000000007) *
               ncr[placed + 1 - j][slots - rejc]) %
              1000000007;
          dp[i][j + siz[i] - slots - rejc] %= 1000000007;
        }
      }
    }
  }
  long long ans = dp[p - 1][0];
  for (i = 0; i < p; i++) {
    ans = (ans * fac[siz[i]]) % 1000000007;
  }
  printf("%lld\n", ans);
  return 0;
}

```