#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int n, num;
int a[305], b[305], cnt[305], sum[305];
long long f[305], c[305][305], dp[305][305];
void cal() {
  for (int i = 0; i <= 300; i++) c[i][0] = 1;
  for (int i = 1; i <= 300; i++)
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  f[0] = 1;
  for (int i = 1; i <= 300; i++) f[i] = f[i - 1] * i % mod;
}
int main() {
  cal();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 2; j * j <= a[i]; j++)
      while (a[i] % (j * j) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    if (a[i] == b[num])
      cnt[num]++, sum[num]++;
    else
      b[++num] = a[i], cnt[num] = 1, sum[num] = sum[num - 1] + 1;
  }
  dp[1][cnt[1] - 1] = f[cnt[1]];
  for (int i = 1; i < num; i++)
    for (int j = 0; j < sum[i]; j++) {
      if (!dp[i][j]) continue;
      for (int k = 0; k <= min(j, cnt[i + 1]); k++)
        for (int l = 0; l <= cnt[i + 1] - k; l++) {
          if (j + l - k < 0 || j + l - k >= sum[i + 1]) continue;
          dp[i + 1][j + l - k] += dp[i][j] * c[j][k] % mod *
                                  c[sum[i] - j + 1][cnt[i + 1] - l - k] % mod *
                                  f[cnt[i + 1]] % mod *
                                  c[cnt[i + 1] - 1][cnt[i + 1] - l - 1] % mod;
          dp[i + 1][j + l - k] %= mod;
        }
    }
  printf("%lld", dp[num][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;
const long long mod = 1e9 + 7;
int n, num;
int a[305], b[305], cnt[305], sum[305];
long long f[305], c[305][305], dp[305][305];
void cal() {
  for (int i = 0; i <= 300; i++) c[i][0] = 1;
  for (int i = 1; i <= 300; i++)
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  f[0] = 1;
  for (int i = 1; i <= 300; i++) f[i] = f[i - 1] * i % mod;
}
int main() {
  cal();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 2; j * j <= a[i]; j++)
      while (a[i] % (j * j) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    if (a[i] == b[num])
      cnt[num]++, sum[num]++;
    else
      b[++num] = a[i], cnt[num] = 1, sum[num] = sum[num - 1] + 1;
  }
  dp[1][cnt[1] - 1] = f[cnt[1]];
  for (int i = 1; i < num; i++)
    for (int j = 0; j < sum[i]; j++) {
      if (!dp[i][j]) continue;
      for (int k = 0; k <= min(j, cnt[i + 1]); k++)
        for (int l = 0; l <= cnt[i + 1] - k; l++) {
          if (j + l - k < 0 || j + l - k >= sum[i + 1]) continue;
          dp[i + 1][j + l - k] += dp[i][j] * c[j][k] % mod *
                                  c[sum[i] - j + 1][cnt[i + 1] - l - k] % mod *
                                  f[cnt[i + 1]] % mod *
                                  c[cnt[i + 1] - 1][cnt[i + 1] - l - 1] % mod;
          dp[i + 1][j + l - k] %= mod;
        }
    }
  printf("%lld", dp[num][0]);
}

```