#include <bits/stdc++.h>
using namespace std;
const int N = 310, P = 1e9 + 7;
int n, a[N], dp[N][N][N], tmp[N];
void add(int &a, int64_t b) { a = (a + b) % P; }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int t;
    scanf("%d", &t);
    a[i] = 1;
    for (int j = 2; j * j <= t; ++j)
      if (t % j == 0) {
        int cnt = 0;
        while (t % j == 0) ++cnt, t /= j;
        if (cnt & 1) a[i] *= j;
      }
    if (t > 1) a[i] *= t;
  }
  sort(a + 1, a + 1 + n);
  dp[0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    int j = i;
    while (j + 1 <= n && a[j + 1] == a[i]) ++j;
    for (int k = i; k <= j; ++k) {
      for (int x = 0; x <= i; ++x) {
        for (int y = 0; y <= k - i; ++y) {
          int &ret = dp[k - 1][x][y];
          if (!ret) continue;
          if (x) add(dp[k][x - 1][y], ret * (int64_t)x);
          if (2 * k - 2 * i - y > 0)
            add(dp[k][x][y + 1], ret * (int64_t)(2 * k - 2 * i - y));
          if (-x - k + 2 * i + y > 0)
            add(dp[k][x][y], ret * (int64_t)(-x - k + 2 * i + y));
        }
      }
    }
    for (int t = 0; t <= j; ++t) tmp[t] = 0;
    for (int x = 0; x <= i; ++x)
      for (int y = 0; y <= j - i; ++y)
        add(tmp[x + y], dp[j][x][y]), dp[j][x][y] = 0;
    for (int x = 0; x <= j; ++x) dp[j][x][0] = tmp[x];
    i = j;
  }
  printf("%d\n", dp[n][0][0]);
}

### Prompt

Please create a solution in cpp 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 N = 310, P = 1e9 + 7;
int n, a[N], dp[N][N][N], tmp[N];
void add(int &a, int64_t b) { a = (a + b) % P; }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int t;
    scanf("%d", &t);
    a[i] = 1;
    for (int j = 2; j * j <= t; ++j)
      if (t % j == 0) {
        int cnt = 0;
        while (t % j == 0) ++cnt, t /= j;
        if (cnt & 1) a[i] *= j;
      }
    if (t > 1) a[i] *= t;
  }
  sort(a + 1, a + 1 + n);
  dp[0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    int j = i;
    while (j + 1 <= n && a[j + 1] == a[i]) ++j;
    for (int k = i; k <= j; ++k) {
      for (int x = 0; x <= i; ++x) {
        for (int y = 0; y <= k - i; ++y) {
          int &ret = dp[k - 1][x][y];
          if (!ret) continue;
          if (x) add(dp[k][x - 1][y], ret * (int64_t)x);
          if (2 * k - 2 * i - y > 0)
            add(dp[k][x][y + 1], ret * (int64_t)(2 * k - 2 * i - y));
          if (-x - k + 2 * i + y > 0)
            add(dp[k][x][y], ret * (int64_t)(-x - k + 2 * i + y));
        }
      }
    }
    for (int t = 0; t <= j; ++t) tmp[t] = 0;
    for (int x = 0; x <= i; ++x)
      for (int y = 0; y <= j - i; ++y)
        add(tmp[x + y], dp[j][x][y]), dp[j][x][y] = 0;
    for (int x = 0; x <= j; ++x) dp[j][x][0] = tmp[x];
    i = j;
  }
  printf("%d\n", dp[n][0][0]);
}

```