#include <bits/stdc++.h>
using namespace std;
const int MAXN = 310;
const int P = 1e9 + 7;
int n, a[MAXN];
long long dp[MAXN][MAXN], Index;
inline int min(int x, int y) {
  if (x < y) return x;
  return y;
}
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j <= 32000; j++) {
      if (a[i] < (j * j)) break;
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
    }
  }
  sort(a + 1, a + n + 1);
  long long tmp[MAXN][MAXN];
  dp[0][0] = 1;
  int last = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) tmp[j][k] = 0;
    if (a[i] == a[i - 1]) {
      for (int j = 0; j <= n; j++)
        for (int k = 0; k <= n; k++) {
          if (j + k <= i) {
            if (k != 0) tmp[j][k - 1] += dp[j][k] * k, tmp[j][k - 1] %= P;
            tmp[j + 1][k] += dp[j][k] * (2 * (i - last) - j);
            tmp[j + 1][k] %= P;
            tmp[j][k] += dp[j][k] * (2 * last - i + j - k);
            tmp[j][k] %= P;
          }
        }
    } else {
      for (int j = 0; j <= n; j++)
        for (int k = 0; k <= n; k++) {
          if (j + k <= i) {
            if (j + k != 0)
              tmp[0][j + k - 1] += dp[j][k] * (j + k), tmp[0][j + k - 1] %= P;
            tmp[0][j + k] += dp[j][k] * (i - j - k);
            tmp[0][j + k] %= P;
          }
        }
      last = i;
    }
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) dp[j][k] = tmp[j][k];
  }
  printf("%lld\n", dp[0][0]);
}
int main(int argc, char** argv) {
  init();
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 = 310;
const int P = 1e9 + 7;
int n, a[MAXN];
long long dp[MAXN][MAXN], Index;
inline int min(int x, int y) {
  if (x < y) return x;
  return y;
}
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j <= 32000; j++) {
      if (a[i] < (j * j)) break;
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
    }
  }
  sort(a + 1, a + n + 1);
  long long tmp[MAXN][MAXN];
  dp[0][0] = 1;
  int last = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) tmp[j][k] = 0;
    if (a[i] == a[i - 1]) {
      for (int j = 0; j <= n; j++)
        for (int k = 0; k <= n; k++) {
          if (j + k <= i) {
            if (k != 0) tmp[j][k - 1] += dp[j][k] * k, tmp[j][k - 1] %= P;
            tmp[j + 1][k] += dp[j][k] * (2 * (i - last) - j);
            tmp[j + 1][k] %= P;
            tmp[j][k] += dp[j][k] * (2 * last - i + j - k);
            tmp[j][k] %= P;
          }
        }
    } else {
      for (int j = 0; j <= n; j++)
        for (int k = 0; k <= n; k++) {
          if (j + k <= i) {
            if (j + k != 0)
              tmp[0][j + k - 1] += dp[j][k] * (j + k), tmp[0][j + k - 1] %= P;
            tmp[0][j + k] += dp[j][k] * (i - j - k);
            tmp[0][j + k] %= P;
          }
        }
      last = i;
    }
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) dp[j][k] = tmp[j][k];
  }
  printf("%lld\n", dp[0][0]);
}
int main(int argc, char** argv) {
  init();
  return 0;
}

```