#include <bits/stdc++.h>
using namespace std;
const int mo = 1000000007;
const double pi = acos(-1.0);
int n, a[333], b[333];
long long fac[333], inv[333], f[333][333];
long long Pow(long long x, long long y, long long mo) {
  long long ans = 1;
  for (; y; x = x * x % mo, y >>= 1)
    if (y & 1) ans = ans * x % mo;
  return ans;
}
long long C(int n, int m) { return fac[n] * inv[m] % mo * inv[n - m] % mo; }
int main() {
  scanf("%d", &n);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mo;
  inv[n] = Pow(fac[n], mo - 2, mo);
  for (int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % mo;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 2; j <= round(sqrt(a[i] + 0.5)); j++)
      while ((a[i] % (j * j)) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  int m = 1;
  b[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] != a[i - 1]) m++;
    b[m]++;
  }
  for (int i = 1; i <= b[1]; i++) f[1][i] = C(b[1] - 1, i - 1);
  for (int i = 2; i <= m; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= b[i]; k++)
        if (j - k)
          f[i][j] =
              (f[i][j] + f[i - 1][j - k] * C(j, k) % mo * C(b[i] - 1, k - 1)) %
              mo;
  long long ans = 0, fff = 1;
  for (int i = n; i >= 1; i--) ans = (ans + fff * f[m][i]) % mo, fff *= -1;
  for (int i = 1; i <= m; i++) ans = (ans * fac[b[i]]) % mo;
  ans = (ans + mo) % mo;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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 mo = 1000000007;
const double pi = acos(-1.0);
int n, a[333], b[333];
long long fac[333], inv[333], f[333][333];
long long Pow(long long x, long long y, long long mo) {
  long long ans = 1;
  for (; y; x = x * x % mo, y >>= 1)
    if (y & 1) ans = ans * x % mo;
  return ans;
}
long long C(int n, int m) { return fac[n] * inv[m] % mo * inv[n - m] % mo; }
int main() {
  scanf("%d", &n);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mo;
  inv[n] = Pow(fac[n], mo - 2, mo);
  for (int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % mo;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 2; j <= round(sqrt(a[i] + 0.5)); j++)
      while ((a[i] % (j * j)) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  int m = 1;
  b[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (a[i] != a[i - 1]) m++;
    b[m]++;
  }
  for (int i = 1; i <= b[1]; i++) f[1][i] = C(b[1] - 1, i - 1);
  for (int i = 2; i <= m; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= b[i]; k++)
        if (j - k)
          f[i][j] =
              (f[i][j] + f[i - 1][j - k] * C(j, k) % mo * C(b[i] - 1, k - 1)) %
              mo;
  long long ans = 0, fff = 1;
  for (int i = n; i >= 1; i--) ans = (ans + fff * f[m][i]) % mo, fff *= -1;
  for (int i = 1; i <= m; i++) ans = (ans * fac[b[i]]) % mo;
  ans = (ans + mo) % mo;
  printf("%lld\n", ans);
  return 0;
}

```