#include <bits/stdc++.h>
using namespace std;
int IN() {
  int c, f, x;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  c == '-' ? (f = 1, x = 0) : (f = 0, x = c - '0');
  while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + c - '0';
  return !f ? x : -x;
}
const int N = 300 + 19;
const int p = 1e9 + 7;
int C[2 * N][2 * N];
int A[N], val[N], dp[N][N], sum[N], fac[N];
int n, x, y, m, res;
void Upd(int &x, long long y) { x = (x + y) % p; }
void Init() {
  n = IN();
  for (int i = 1; i < n + 1; i++) {
    x = IN();
    y = 1;
    for (int u = 2; u * u <= x; u++)
      if (x % u == 0) {
        int c = 0;
        while (x % u == 0) x /= u, c++;
        if (c & 1) y *= u;
      }
    if (x > 1) y *= x;
    int b = 0;
    for (int j = 1; j < m + 1; j++)
      if (val[j] == y) {
        A[j]++;
        b = 1;
        break;
      }
    if (!b) {
      val[++m] = y;
      A[m] = 1;
    }
  }
  sum[0] = 1;
  for (int i = 1; i < m + 1; i++) sum[i] = sum[i - 1] + A[i];
}
int main() {
  for (int i = 0; i < 2 * N; i++) {
    C[i][0] = 1;
    for (int j = 1; j < i + 1; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
  }
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % p;
  Init();
  dp[0][0] = 1;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < N; j++)
      if (dp[i][j]) {
        for (int x = 0; x <= j && x <= A[i + 1]; x++)
          for (int y = 0; y <= sum[i] - j && x + y <= A[i + 1]; y++) {
            Upd(dp[i + 1][j - x + A[i + 1] - x - y],
                1ll * dp[i][j] * C[j][x] % p * C[sum[i] - j][y] % p *
                    C[A[i + 1] - 1][x + y - 1]);
          }
      }
  }
  res = dp[m][0];
  for (int i = 1; i < m + 1; i++) res = 1ll * res * fac[A[i]] % p;
  printf("%d\n", res);
}

### Prompt

In CPP, your task is to solve 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;
int IN() {
  int c, f, x;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  c == '-' ? (f = 1, x = 0) : (f = 0, x = c - '0');
  while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + c - '0';
  return !f ? x : -x;
}
const int N = 300 + 19;
const int p = 1e9 + 7;
int C[2 * N][2 * N];
int A[N], val[N], dp[N][N], sum[N], fac[N];
int n, x, y, m, res;
void Upd(int &x, long long y) { x = (x + y) % p; }
void Init() {
  n = IN();
  for (int i = 1; i < n + 1; i++) {
    x = IN();
    y = 1;
    for (int u = 2; u * u <= x; u++)
      if (x % u == 0) {
        int c = 0;
        while (x % u == 0) x /= u, c++;
        if (c & 1) y *= u;
      }
    if (x > 1) y *= x;
    int b = 0;
    for (int j = 1; j < m + 1; j++)
      if (val[j] == y) {
        A[j]++;
        b = 1;
        break;
      }
    if (!b) {
      val[++m] = y;
      A[m] = 1;
    }
  }
  sum[0] = 1;
  for (int i = 1; i < m + 1; i++) sum[i] = sum[i - 1] + A[i];
}
int main() {
  for (int i = 0; i < 2 * N; i++) {
    C[i][0] = 1;
    for (int j = 1; j < i + 1; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
  }
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % p;
  Init();
  dp[0][0] = 1;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < N; j++)
      if (dp[i][j]) {
        for (int x = 0; x <= j && x <= A[i + 1]; x++)
          for (int y = 0; y <= sum[i] - j && x + y <= A[i + 1]; y++) {
            Upd(dp[i + 1][j - x + A[i + 1] - x - y],
                1ll * dp[i][j] * C[j][x] % p * C[sum[i] - j][y] % p *
                    C[A[i + 1] - 1][x + y - 1]);
          }
      }
  }
  res = dp[m][0];
  for (int i = 1; i < m + 1; i++) res = 1ll * res * fac[A[i]] % p;
  printf("%d\n", res);
}

```