#include <bits/stdc++.h>
using namespace std;
int n, x, p = 1000000007;
int b[320], cnt;
int c[320][320];
int f[320][320];
map<int, int> g;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    for (int i = 2; i * i <= x; i++) {
      while (x % (i * i) == 0) {
        x /= i * i;
      }
    }
    g[x]++;
  }
  for (int i = 0; i <= 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]) % p;
    }
  }
  for (pair<int, int> i : g) {
    b[cnt++] = i.second;
  }
  f[0][0] = 1;
  int tot = 0;
  for (int i = 0; i < cnt; i++) {
    for (int j = 0; j <= tot; j++) {
      if (f[i][j] == 0) {
        continue;
      }
      for (int k = 1; k <= min(b[i], tot + 1); k++) {
        for (int l = 0; l <= min(j, k); l++) {
          int &t = f[i + 1][j - l + b[i] - k];
          long long d = f[i][j];
          d = (d * c[b[i] - 1][k - 1]) % p;
          d = (d * c[j][l]) % p;
          d = (d * c[tot - j + 1][k - l]) % p;
          t = (t + d) % p;
        }
      }
    }
    tot += b[i];
  }
  int z = f[cnt][0];
  for (pair<int, int> i : g) {
    for (int j = 1; j <= i.second; j++) {
      z = (long long)z * j % p;
    }
  }
  printf("%d\n", z);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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, x, p = 1000000007;
int b[320], cnt;
int c[320][320];
int f[320][320];
map<int, int> g;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    for (int i = 2; i * i <= x; i++) {
      while (x % (i * i) == 0) {
        x /= i * i;
      }
    }
    g[x]++;
  }
  for (int i = 0; i <= 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]) % p;
    }
  }
  for (pair<int, int> i : g) {
    b[cnt++] = i.second;
  }
  f[0][0] = 1;
  int tot = 0;
  for (int i = 0; i < cnt; i++) {
    for (int j = 0; j <= tot; j++) {
      if (f[i][j] == 0) {
        continue;
      }
      for (int k = 1; k <= min(b[i], tot + 1); k++) {
        for (int l = 0; l <= min(j, k); l++) {
          int &t = f[i + 1][j - l + b[i] - k];
          long long d = f[i][j];
          d = (d * c[b[i] - 1][k - 1]) % p;
          d = (d * c[j][l]) % p;
          d = (d * c[tot - j + 1][k - l]) % p;
          t = (t + d) % p;
        }
      }
    }
    tot += b[i];
  }
  int z = f[cnt][0];
  for (pair<int, int> i : g) {
    for (int j = 1; j <= i.second; j++) {
      z = (long long)z * j % p;
    }
  }
  printf("%d\n", z);
  return 0;
}

```