#include <bits/stdc++.h>
using namespace std;
const int iinf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
void fmod(int& first) { first += first >> 31 & mod; }
const int N = 300;
int n, a[N], f[2][N][N];
map<int, int> mp;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = (0), iE = (n); i < iE; i++) {
    cin >> a[i];
    for (int d = 2; d * d <= a[i]; d++)
      if (!(a[i] % d))
        while (!(a[i] % (d * d))) a[i] /= (d * d);
    mp[a[i]]++;
  }
  int t = 0, cnt = 0;
  for (int i = (0), iE = (n); i < iE; i++)
    for (int j = (0), jE = (n); j < jE; j++) f[t][i][j] = 0;
  f[t][0][0] = 1;
  for (const pair<int, int>& u : mp) {
    t ^= 1, cnt++;
    for (int i = (0), iE = (n); i < iE; i++)
      for (int j = (0), jE = (n); j < jE; j++) f[t][i][j] = 0;
    for (int i = (0), iE = (n); i < iE; i++)
      for (int j = (0), jE = (i + 1); j < jE; j++)
        if (f[t ^ 1][i][j])
          (cnt - i) &&
              (fmod(f[t][i][0] += 1ll * (cnt - i) * f[t ^ 1][i][j] % mod - mod),
               true),
              i &&
                  (fmod(f[t][i - 1][0] += 1ll * i * f[t ^ 1][i][j] % mod - mod),
                   true);
    for (int pre = (1), preE = (u.second); pre < preE; pre++) {
      t ^= 1, cnt++;
      for (int i = (0), iE = (n); i < iE; i++)
        for (int j = (0), jE = (n); j < jE; j++) f[t][i][j] = 0;
      for (int i = (0), iE = (n); i < iE; i++)
        for (int j = (0), jE = (i + 1); j < jE; j++)
          if (f[t ^ 1][i][j])
            (2 * pre - j) &&
                (fmod(f[t][i + 1][j + 1] +=
                      1ll * (2 * pre - j) * f[t ^ 1][i][j] % mod - mod),
                 true),
                (i - j) && (fmod(f[t][i - 1][j] +=
                                 1ll * (i - j) * f[t ^ 1][i][j] % mod - mod),
                            true),
                (cnt - (2 * pre - j) - (i - j)) &&
                    (fmod(f[t][i][j] += 1ll * (cnt - (2 * pre - j) - (i - j)) *
                                            f[t ^ 1][i][j] % mod -
                                        mod),
                     true);
    }
  }
  cout << f[t][0][0] << '\n';
  return 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 int iinf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
void fmod(int& first) { first += first >> 31 & mod; }
const int N = 300;
int n, a[N], f[2][N][N];
map<int, int> mp;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = (0), iE = (n); i < iE; i++) {
    cin >> a[i];
    for (int d = 2; d * d <= a[i]; d++)
      if (!(a[i] % d))
        while (!(a[i] % (d * d))) a[i] /= (d * d);
    mp[a[i]]++;
  }
  int t = 0, cnt = 0;
  for (int i = (0), iE = (n); i < iE; i++)
    for (int j = (0), jE = (n); j < jE; j++) f[t][i][j] = 0;
  f[t][0][0] = 1;
  for (const pair<int, int>& u : mp) {
    t ^= 1, cnt++;
    for (int i = (0), iE = (n); i < iE; i++)
      for (int j = (0), jE = (n); j < jE; j++) f[t][i][j] = 0;
    for (int i = (0), iE = (n); i < iE; i++)
      for (int j = (0), jE = (i + 1); j < jE; j++)
        if (f[t ^ 1][i][j])
          (cnt - i) &&
              (fmod(f[t][i][0] += 1ll * (cnt - i) * f[t ^ 1][i][j] % mod - mod),
               true),
              i &&
                  (fmod(f[t][i - 1][0] += 1ll * i * f[t ^ 1][i][j] % mod - mod),
                   true);
    for (int pre = (1), preE = (u.second); pre < preE; pre++) {
      t ^= 1, cnt++;
      for (int i = (0), iE = (n); i < iE; i++)
        for (int j = (0), jE = (n); j < jE; j++) f[t][i][j] = 0;
      for (int i = (0), iE = (n); i < iE; i++)
        for (int j = (0), jE = (i + 1); j < jE; j++)
          if (f[t ^ 1][i][j])
            (2 * pre - j) &&
                (fmod(f[t][i + 1][j + 1] +=
                      1ll * (2 * pre - j) * f[t ^ 1][i][j] % mod - mod),
                 true),
                (i - j) && (fmod(f[t][i - 1][j] +=
                                 1ll * (i - j) * f[t ^ 1][i][j] % mod - mod),
                            true),
                (cnt - (2 * pre - j) - (i - j)) &&
                    (fmod(f[t][i][j] += 1ll * (cnt - (2 * pre - j) - (i - j)) *
                                            f[t ^ 1][i][j] % mod -
                                        mod),
                     true);
    }
  }
  cout << f[t][0][0] << '\n';
  return 0;
}

```