#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 350;
int c[2 * N][2 * N], dp[N][N], b[N];
int f[N];
map<int, int> bucket;
int min(int a, int b) { return a > b ? b : a; }
int main() {
  int n, i, j, a;
  scanf("%i", &n);
  f[0] = 1;
  for (i = 1; i <= n; i++) {
    scanf("%i", &a);
    for (j = 2; j * j <= a; j++)
      while (a % (j * j) == 0) a /= j * j;
    bucket[a]++;
    f[i] = ((long long)f[i - 1] * i) % mod;
  }
  for (i = 0; i < 2 * n; i++) {
    c[i][0] = 1;
    for (j = 1; j <= i; j++) {
      c[i][j] = ((long long)c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  int m = 0, k, l, s = 0;
  long long sol = 1;
  map<int, int>::iterator it;
  for (it = bucket.begin(); it != bucket.end(); it++) b[++m] = it->second;
  dp[0][0] = 1;
  for (i = 0; i < m; i++) {
    for (j = 0; j <= n; j++) {
      if (dp[i][j] > 0) {
        for (k = 1; k <= b[i + 1]; k++) {
          for (l = 0; l <= min(j, k); l++) {
            long long tmp = ((long long)dp[i][j] * c[j][l]) % mod;
            tmp = (tmp * c[s + 1 - j][k - l]) % mod;
            tmp = (tmp * c[b[i + 1] - 1][k - 1]) % mod;
            dp[i + 1][j + b[i + 1] - k - l] =
                ((long long)dp[i + 1][j + b[i + 1] - k - l] + tmp) % mod;
          }
        }
      }
    }
    s += b[i + 1];
    sol = ((long long)sol * f[b[i + 1]]) % mod;
  }
  printf("%lld\n", (sol * dp[m][0]) % mod);
  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;
const int mod = 1e9 + 7;
const int N = 350;
int c[2 * N][2 * N], dp[N][N], b[N];
int f[N];
map<int, int> bucket;
int min(int a, int b) { return a > b ? b : a; }
int main() {
  int n, i, j, a;
  scanf("%i", &n);
  f[0] = 1;
  for (i = 1; i <= n; i++) {
    scanf("%i", &a);
    for (j = 2; j * j <= a; j++)
      while (a % (j * j) == 0) a /= j * j;
    bucket[a]++;
    f[i] = ((long long)f[i - 1] * i) % mod;
  }
  for (i = 0; i < 2 * n; i++) {
    c[i][0] = 1;
    for (j = 1; j <= i; j++) {
      c[i][j] = ((long long)c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  int m = 0, k, l, s = 0;
  long long sol = 1;
  map<int, int>::iterator it;
  for (it = bucket.begin(); it != bucket.end(); it++) b[++m] = it->second;
  dp[0][0] = 1;
  for (i = 0; i < m; i++) {
    for (j = 0; j <= n; j++) {
      if (dp[i][j] > 0) {
        for (k = 1; k <= b[i + 1]; k++) {
          for (l = 0; l <= min(j, k); l++) {
            long long tmp = ((long long)dp[i][j] * c[j][l]) % mod;
            tmp = (tmp * c[s + 1 - j][k - l]) % mod;
            tmp = (tmp * c[b[i + 1] - 1][k - 1]) % mod;
            dp[i + 1][j + b[i + 1] - k - l] =
                ((long long)dp[i + 1][j + b[i + 1] - k - l] + tmp) % mod;
          }
        }
      }
    }
    s += b[i + 1];
    sol = ((long long)sol * f[b[i + 1]]) % mod;
  }
  printf("%lld\n", (sol * dp[m][0]) % mod);
  return 0;
}

```