#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 500;
int n, x, a[N], C[N][N], now, cnt[N];
long long f[N][N], fac[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    for (int j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) x /= j * j;
    }
    a[i] = x;
  }
  sort(a + 1, a + n + 1);
  int now = 0;
  for (int i = 1; i <= n; i++)
    if (a[i] == a[i - 1])
      cnt[now]++;
    else
      cnt[++now]++;
  f[1][cnt[1] - 1] = 1;
  fac[1] = 1;
  for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
  C[0][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= i; j++)
      C[i][j] = j == 0 ? 1 : (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  for (int i = 2, sum = cnt[1]; i <= now; i++, sum += cnt[i - 1])
    for (int j = 0; j < sum; j++)
      for (int k = 1; k <= cnt[i]; k++)
        for (int l = 0; l <= min(k, j); l++)
          f[i][j + cnt[i] - k - l] =
              (f[i][j + cnt[i] - k - l] + f[i - 1][j] * C[j][l] % MOD *
                                              C[cnt[i] - 1][k - 1] % MOD *
                                              C[sum - j + 1][k - l] % MOD) %
              MOD;
  long long ans = f[now][0];
  for (int i = 1; i <= now; i++) ans = (ans * fac[cnt[i]]) % MOD;
  printf("%I64d\n", ans);
}

### Prompt

Please provide a Cpp coded solution 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 = 500;
int n, x, a[N], C[N][N], now, cnt[N];
long long f[N][N], fac[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    for (int j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) x /= j * j;
    }
    a[i] = x;
  }
  sort(a + 1, a + n + 1);
  int now = 0;
  for (int i = 1; i <= n; i++)
    if (a[i] == a[i - 1])
      cnt[now]++;
    else
      cnt[++now]++;
  f[1][cnt[1] - 1] = 1;
  fac[1] = 1;
  for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
  C[0][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= i; j++)
      C[i][j] = j == 0 ? 1 : (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  for (int i = 2, sum = cnt[1]; i <= now; i++, sum += cnt[i - 1])
    for (int j = 0; j < sum; j++)
      for (int k = 1; k <= cnt[i]; k++)
        for (int l = 0; l <= min(k, j); l++)
          f[i][j + cnt[i] - k - l] =
              (f[i][j + cnt[i] - k - l] + f[i - 1][j] * C[j][l] % MOD *
                                              C[cnt[i] - 1][k - 1] % MOD *
                                              C[sum - j + 1][k - l] % MOD) %
              MOD;
  long long ans = f[now][0];
  for (int i = 1; i <= now; i++) ans = (ans * fac[cnt[i]]) % MOD;
  printf("%I64d\n", ans);
}

```