#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long b[500], a[500];
long long A[600];
long long dp[1000][1000];
long long C[600][600];
void Init() {
  for (int i = 0; i < 550; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
  A[0] = 1;
  for (int i = 1; i < 550; i++) A[i] = (A[i - 1] * i) % MOD;
}
int main() {
  Init();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &b[i]);
  }
  for (int i = 1; i <= n; i++) {
    int t = b[i];
    for (int j = 2; j * j <= b[i]; j++) {
      while (t % (j * j) == 0) {
        t /= (j * j);
      }
    }
    b[i] = t;
  }
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  sort(b + 1, b + 1 + n);
  int cnt = 1;
  for (int i = 1; i <= n; i++) {
    if (i == n) {
      a[cnt]++;
    } else if (b[i] == b[i + 1]) {
      a[cnt]++;
    } else {
      a[cnt]++;
      cnt++;
    }
  }
  n = cnt;
  memset(dp, 0, sizeof(dp));
  dp[1][a[1] - 1] = 1;
  long long sum = a[1];
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < sum; j++)
      for (int k = 1; k <= a[i]; k++)
        for (int u = 0; u <= j && u <= k; u++)
          dp[i][j - u + a[i] - 1 - (k - 1)] =
              (dp[i][j - u + a[i] - k] +
               (((dp[i - 1][j] * C[j][u]) % MOD * C[sum + 1 - j][k - u]) % MOD *
                C[a[i] - 1][k - 1]) %
                   MOD) %
              MOD;
    sum += a[i];
  }
  long long ans = dp[n][0];
  for (int i = 1; i <= n; i++) ans = (ans * A[a[i]]) % MOD;
  cout << ans << endl;
}

### 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 int MOD = 1e9 + 7;
long long b[500], a[500];
long long A[600];
long long dp[1000][1000];
long long C[600][600];
void Init() {
  for (int i = 0; i < 550; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
  A[0] = 1;
  for (int i = 1; i < 550; i++) A[i] = (A[i - 1] * i) % MOD;
}
int main() {
  Init();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &b[i]);
  }
  for (int i = 1; i <= n; i++) {
    int t = b[i];
    for (int j = 2; j * j <= b[i]; j++) {
      while (t % (j * j) == 0) {
        t /= (j * j);
      }
    }
    b[i] = t;
  }
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  sort(b + 1, b + 1 + n);
  int cnt = 1;
  for (int i = 1; i <= n; i++) {
    if (i == n) {
      a[cnt]++;
    } else if (b[i] == b[i + 1]) {
      a[cnt]++;
    } else {
      a[cnt]++;
      cnt++;
    }
  }
  n = cnt;
  memset(dp, 0, sizeof(dp));
  dp[1][a[1] - 1] = 1;
  long long sum = a[1];
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < sum; j++)
      for (int k = 1; k <= a[i]; k++)
        for (int u = 0; u <= j && u <= k; u++)
          dp[i][j - u + a[i] - 1 - (k - 1)] =
              (dp[i][j - u + a[i] - k] +
               (((dp[i - 1][j] * C[j][u]) % MOD * C[sum + 1 - j][k - u]) % MOD *
                C[a[i] - 1][k - 1]) %
                   MOD) %
              MOD;
    sum += a[i];
  }
  long long ans = dp[n][0];
  for (int i = 1; i <= n; i++) ans = (ans * A[a[i]]) % MOD;
  cout << ans << endl;
}

```