#include <bits/stdc++.h>
using namespace std;
const long long Mod = 1e9 + 7;
long long n, col[305], dp[305][305][305];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> col[i];
    for (long long j = 2; j * j <= col[i]; j++)
      while (col[i] % (j * j) == 0) col[i] /= j * j;
  }
  sort(col + 1, col + n + 1);
  dp[1][0][0] = 1;
  for (int i = 1, cnt = 0; i <= n; i++) {
    if (col[i] != col[i - 1]) {
      for (int j = 0; j <= i; j++)
        for (int k = 1; k <= cnt; k++) {
          dp[i - 1][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][k]) % Mod;
          dp[i - 1][j][k] = 0;
        }
      cnt = 0;
    }
    for (int j = 0; j <= i; j++)
      for (int k = 0; k <= min(cnt, j); k++) {
        if (j && k)
          dp[i][j][k] = (dp[i][j][k] +
                         dp[i - 1][j - 1][k - 1] * (cnt * 2 - k + 1) % Mod) %
                        Mod;
        dp[i][j][k] =
            (dp[i][j][k] + dp[i - 1][j + 1][k] * (j - k + 1) % Mod) % Mod;
        dp[i][j][k] =
            (dp[i][j][k] +
             (dp[i - 1][j][k] * (i - (cnt * 2 - k) - (j - k)) % Mod + Mod) %
                 Mod) %
            Mod;
      }
    cnt++;
  }
  cout << dp[n][0][0];
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
long long n, col[305], dp[305][305][305];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> col[i];
    for (long long j = 2; j * j <= col[i]; j++)
      while (col[i] % (j * j) == 0) col[i] /= j * j;
  }
  sort(col + 1, col + n + 1);
  dp[1][0][0] = 1;
  for (int i = 1, cnt = 0; i <= n; i++) {
    if (col[i] != col[i - 1]) {
      for (int j = 0; j <= i; j++)
        for (int k = 1; k <= cnt; k++) {
          dp[i - 1][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][k]) % Mod;
          dp[i - 1][j][k] = 0;
        }
      cnt = 0;
    }
    for (int j = 0; j <= i; j++)
      for (int k = 0; k <= min(cnt, j); k++) {
        if (j && k)
          dp[i][j][k] = (dp[i][j][k] +
                         dp[i - 1][j - 1][k - 1] * (cnt * 2 - k + 1) % Mod) %
                        Mod;
        dp[i][j][k] =
            (dp[i][j][k] + dp[i - 1][j + 1][k] * (j - k + 1) % Mod) % Mod;
        dp[i][j][k] =
            (dp[i][j][k] +
             (dp[i - 1][j][k] * (i - (cnt * 2 - k) - (j - k)) % Mod + Mod) %
                 Mod) %
            Mod;
      }
    cnt++;
  }
  cout << dp[n][0][0];
}

```