#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1e9) + 7;
int n;
vector<int> a, b, ls, sum;
long long C[301][301], fact[301], dp[301][301];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  C[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
  for (int i = 0, x; i < n; i++) {
    cin >> x;
    a.push_back(x);
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < n; i++) {
    b.push_back(i);
    for (int j = 0; j < i; j++) {
      long long targ = 1ll * a[i] * a[j];
      if (floor(sqrt(targ)) * floor(sqrt(targ)) == targ) {
        b[i] = j;
        break;
      }
    }
  }
  sort(b.begin(), b.end());
  ls.push_back(0);
  sum.push_back(0);
  int last = 0;
  for (int i = 0; i < n; i++) {
    if (i > 0 && b[i] != b[i - 1]) {
      ls.push_back(i - last);
      sum.push_back(sum.back() + i - last);
      last = i;
    }
  }
  ls.push_back(n - last);
  sum.push_back(sum.back() + n - last);
  dp[0][0] = 1;
  for (int x = 1; x < ls.size(); x++) {
    for (int ij = 0; ij <= ls[x]; ij++) {
      for (int y = 0; y <= sum[x - 1] + 1; y++)
        if (dp[x - 1][y]) {
          for (int j = 0; j <= min(ij, y); j++) {
            int i = ij - j;
            int z = sum[x - 1] + 1 - y;
            dp[x][y - j + ls[x] - ij] += dp[x - 1][y] * C[z][i] % MOD *
                                         C[y][j] % MOD * C[ls[x] - 1][ij - 1] %
                                         MOD;
            dp[x][y - j + ls[x] - ij] %= MOD;
          }
        }
    }
  }
  long long ans = dp[ls.size() - 1][0];
  for (int i = 1; i < ls.size(); i++) ans = (ans * fact[ls[i]]) % MOD;
  cout << 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 long long MOD = (1e9) + 7;
int n;
vector<int> a, b, ls, sum;
long long C[301][301], fact[301], dp[301][301];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  C[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
  for (int i = 0, x; i < n; i++) {
    cin >> x;
    a.push_back(x);
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < n; i++) {
    b.push_back(i);
    for (int j = 0; j < i; j++) {
      long long targ = 1ll * a[i] * a[j];
      if (floor(sqrt(targ)) * floor(sqrt(targ)) == targ) {
        b[i] = j;
        break;
      }
    }
  }
  sort(b.begin(), b.end());
  ls.push_back(0);
  sum.push_back(0);
  int last = 0;
  for (int i = 0; i < n; i++) {
    if (i > 0 && b[i] != b[i - 1]) {
      ls.push_back(i - last);
      sum.push_back(sum.back() + i - last);
      last = i;
    }
  }
  ls.push_back(n - last);
  sum.push_back(sum.back() + n - last);
  dp[0][0] = 1;
  for (int x = 1; x < ls.size(); x++) {
    for (int ij = 0; ij <= ls[x]; ij++) {
      for (int y = 0; y <= sum[x - 1] + 1; y++)
        if (dp[x - 1][y]) {
          for (int j = 0; j <= min(ij, y); j++) {
            int i = ij - j;
            int z = sum[x - 1] + 1 - y;
            dp[x][y - j + ls[x] - ij] += dp[x - 1][y] * C[z][i] % MOD *
                                         C[y][j] % MOD * C[ls[x] - 1][ij - 1] %
                                         MOD;
            dp[x][y - j + ls[x] - ij] %= MOD;
          }
        }
    }
  }
  long long ans = dp[ls.size() - 1][0];
  for (int i = 1; i < ls.size(); i++) ans = (ans * fact[ls[i]]) % MOD;
  cout << ans;
}

```