#include <bits/stdc++.h>
using namespace std;
int read() {
  int f = 1, x = 0;
  char c = getchar();
  while (c < '0' || '9' < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return f * x;
}
const int Mod = int(1e9 + 7);
inline int Add(int a, int b) {
  a += b;
  return a >= Mod ? a - Mod : a;
}
int C[1000 + 5][1000 + 5], f[1000 + 5][1000 + 5];
void Prepare() {
  C[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= 1000; j++) C[i][j] = Add(C[i - 1][j], C[i - 1][j - 1]);
  }
  return;
}
map<int, int> Bar;
int main() {
  Prepare();
  int n = read(), K = 0, m = 0, ans = 1;
  for (int i = 1; i <= n; i++) {
    int a = read();
    for (int j = 2; j * j <= a; j++)
      while (a % (j * j) == 0) a /= j * j;
    if (!Bar.count(a)) K++;
    Bar[a]++;
    ans = 1ll * ans * Bar[a] % Mod;
  }
  f[0][0] = 1;
  int i = 1;
  for (map<int, int>::iterator it = Bar.begin(); it != Bar.end(); it++, i++) {
    int c = it->second;
    for (int j = 0; j <= m; j++)
      if (f[i - 1][j]) {
        for (int k = 1; k <= c; k++)
          for (int l = 0; l <= min(k, j); l++)
            f[i][j - l + c - k] =
                Add(f[i][j - l + c - k], 1ll * f[i - 1][j] * C[c - 1][k - 1] %
                                             Mod * C[j][l] % Mod *
                                             C[m - j + 1][k - l] % Mod);
      }
    m += c;
  }
  printf("%lld\n", 1ll * ans * f[K][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 read() {
  int f = 1, x = 0;
  char c = getchar();
  while (c < '0' || '9' < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return f * x;
}
const int Mod = int(1e9 + 7);
inline int Add(int a, int b) {
  a += b;
  return a >= Mod ? a - Mod : a;
}
int C[1000 + 5][1000 + 5], f[1000 + 5][1000 + 5];
void Prepare() {
  C[0][0] = 1;
  for (int i = 1; i <= 1000; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= 1000; j++) C[i][j] = Add(C[i - 1][j], C[i - 1][j - 1]);
  }
  return;
}
map<int, int> Bar;
int main() {
  Prepare();
  int n = read(), K = 0, m = 0, ans = 1;
  for (int i = 1; i <= n; i++) {
    int a = read();
    for (int j = 2; j * j <= a; j++)
      while (a % (j * j) == 0) a /= j * j;
    if (!Bar.count(a)) K++;
    Bar[a]++;
    ans = 1ll * ans * Bar[a] % Mod;
  }
  f[0][0] = 1;
  int i = 1;
  for (map<int, int>::iterator it = Bar.begin(); it != Bar.end(); it++, i++) {
    int c = it->second;
    for (int j = 0; j <= m; j++)
      if (f[i - 1][j]) {
        for (int k = 1; k <= c; k++)
          for (int l = 0; l <= min(k, j); l++)
            f[i][j - l + c - k] =
                Add(f[i][j - l + c - k], 1ll * f[i - 1][j] * C[c - 1][k - 1] %
                                             Mod * C[j][l] % Mod *
                                             C[m - j + 1][k - l] % Mod);
      }
    m += c;
  }
  printf("%lld\n", 1ll * ans * f[K][0] % Mod);
  return 0;
}

```