#include <bits/stdc++.h>
using namespace std;
bool is_square(long long int x) {
  long long int p = sqrt(x);
  if (p * p == x)
    return true;
  else
    return false;
}
long long int C[310][310];
long long int n, a[310], d[310][310];
vector<long long int> group[310];
vector<int> num(310);
void cal() {
  C[0][0] = 1;
  long long int i, j;
  for (i = 1; i <= 302; i++) {
    C[i][0] = 1;
    for (j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
    }
  }
}
int main() {
  cin >> n;
  cal();
  int i, j, ij, k, l, x, y;
  for (i = 0; i < n; i++) cin >> a[i];
  int cnt = 0;
  for (i = 0; i < n; i++) {
    bool chk = false;
    for (j = 0; j < cnt; j++) {
      if (is_square(group[j][0] * a[i])) {
        chk = true;
        group[j].push_back(a[i]);
        break;
      }
    }
    if (!chk) {
      group[cnt].push_back(a[i]);
      cnt++;
    }
  }
  for (i = 0; i < cnt; i++) num[i + 1] = group[i].size();
  d[0][0] = 1;
  int sum = 0;
  for (x = 1; x <= cnt; x++) {
    for (ij = 0; ij <= num[x]; ij++) {
      for (y = 0; y <= (sum + 1); y++) {
        if (d[x - 1][y] > 0) {
          for (j = 0; j <= min(ij, y); j++) {
            i = ij - j;
            d[x][(y - j) + (num[x] - ij)] =
                (d[x][(y - j) + (num[x] - ij)] +
                 (d[x - 1][y] *
                  (C[y][j] *
                   (C[sum + 1 - y][i] * (C[num[x] - 1][ij - 1] % 1000000007) %
                    1000000007) %
                   1000000007) %
                  1000000007)) %
                1000000007;
          }
        }
      }
    }
    sum += num[x];
  }
  for (i = 1; i <= cnt; i++) {
    for (j = 1; j <= num[i]; j++) d[cnt][0] = (d[cnt][0] * j) % 1000000007;
  }
  cout << d[cnt][0] << endl;
  return 0;
}

### Prompt

Your challenge is to write 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;
bool is_square(long long int x) {
  long long int p = sqrt(x);
  if (p * p == x)
    return true;
  else
    return false;
}
long long int C[310][310];
long long int n, a[310], d[310][310];
vector<long long int> group[310];
vector<int> num(310);
void cal() {
  C[0][0] = 1;
  long long int i, j;
  for (i = 1; i <= 302; i++) {
    C[i][0] = 1;
    for (j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
    }
  }
}
int main() {
  cin >> n;
  cal();
  int i, j, ij, k, l, x, y;
  for (i = 0; i < n; i++) cin >> a[i];
  int cnt = 0;
  for (i = 0; i < n; i++) {
    bool chk = false;
    for (j = 0; j < cnt; j++) {
      if (is_square(group[j][0] * a[i])) {
        chk = true;
        group[j].push_back(a[i]);
        break;
      }
    }
    if (!chk) {
      group[cnt].push_back(a[i]);
      cnt++;
    }
  }
  for (i = 0; i < cnt; i++) num[i + 1] = group[i].size();
  d[0][0] = 1;
  int sum = 0;
  for (x = 1; x <= cnt; x++) {
    for (ij = 0; ij <= num[x]; ij++) {
      for (y = 0; y <= (sum + 1); y++) {
        if (d[x - 1][y] > 0) {
          for (j = 0; j <= min(ij, y); j++) {
            i = ij - j;
            d[x][(y - j) + (num[x] - ij)] =
                (d[x][(y - j) + (num[x] - ij)] +
                 (d[x - 1][y] *
                  (C[y][j] *
                   (C[sum + 1 - y][i] * (C[num[x] - 1][ij - 1] % 1000000007) %
                    1000000007) %
                   1000000007) %
                  1000000007)) %
                1000000007;
          }
        }
      }
    }
    sum += num[x];
  }
  for (i = 1; i <= cnt; i++) {
    for (j = 1; j <= num[i]; j++) d[cnt][0] = (d[cnt][0] * j) % 1000000007;
  }
  cout << d[cnt][0] << endl;
  return 0;
}

```