#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
struct Num {
  int a;
  Num(int _a = 0) : a(_a) {}
  Num operator+(const Num& _) const {
    int ret = a + _.a;
    return ret < mod ? Num(ret) : Num(ret - mod);
  }
  Num operator-(const Num& _) const { return *this + Num(mod - _.a); }
  Num operator*(const Num& _) const { return Num((int)((LL)a * _.a % mod)); }
  void operator+=(const Num& _) { *this = *this + _; }
  void operator-=(const Num& _) { *this = *this - _; }
  void operator*=(const Num& _) { *this = *this * _; }
};
vector<Num> f;
vector<int> simplify(int val) {
  vector<int> ret;
  for (int i = 2; i * i <= val; ++i)
    if (val % i == 0) {
      bool prt = 0;
      while (val % i == 0) {
        prt ^= 1;
        val /= i;
      }
      if (prt) ret.emplace_back(i);
    }
  if (val > 1) ret.emplace_back(val);
  return ret;
}
int n;
vector<int> a;
vector<vector<int> > com, ele;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  a.assign(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    com.emplace_back(simplify(a[i]));
  }
  sort((com).begin(), (com).end());
  com.erase(unique((com).begin(), (com).end()), com.end());
  ele.assign(((int)(com).size()), {});
  for (int i = 0; i < n; ++i) {
    ele[(int)(lower_bound((com).begin(), (com).end(), simplify(a[i])) -
              com.begin())]
        .emplace_back(i);
  }
  f.assign(1, Num(1));
  int prvGroup = 0;
  for (auto group : ele) {
    vector<vector<Num> > g(((int)(group).size()),
                           vector<Num>(((int)(f).size()), Num()));
    g[0] = f;
    for (int curGroup = 0; curGroup < ((int)(group).size()); ++curGroup) {
      vector<vector<Num> > nG(((int)(g).size()),
                              vector<Num>(((int)(g.back()).size()), Num()));
      for (int i = 0; i < ((int)(g).size()); ++i) {
        for (int j = 0; j < ((int)(g[i]).size()); ++j)
          if (g[i][j].a) {
            if (j) nG[i][j - 1] += g[i][j] * Num(j);
            if (i + 1 < ((int)(g).size()))
              nG[i + 1][j] += g[i][j] * Num((curGroup << 1) - i);
            nG[i][j] += g[i][j] * Num(curGroup + prvGroup + 1 - j -
                                      ((curGroup << 1) - i));
          }
      }
      g.swap(nG);
    }
    prvGroup += ((int)(group).size());
    f.assign(prvGroup, Num());
    for (int i = 0; i < ((int)(g).size()); ++i) {
      for (int j = 0; j < ((int)(g[i]).size()); ++j) f[i + j] += g[i][j];
    }
  }
  cout << f[0].a << '\n';
  cout.flush();
  return 0;
}

### Prompt

Please formulate 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;
using LL = long long;
const int mod = 1e9 + 7;
struct Num {
  int a;
  Num(int _a = 0) : a(_a) {}
  Num operator+(const Num& _) const {
    int ret = a + _.a;
    return ret < mod ? Num(ret) : Num(ret - mod);
  }
  Num operator-(const Num& _) const { return *this + Num(mod - _.a); }
  Num operator*(const Num& _) const { return Num((int)((LL)a * _.a % mod)); }
  void operator+=(const Num& _) { *this = *this + _; }
  void operator-=(const Num& _) { *this = *this - _; }
  void operator*=(const Num& _) { *this = *this * _; }
};
vector<Num> f;
vector<int> simplify(int val) {
  vector<int> ret;
  for (int i = 2; i * i <= val; ++i)
    if (val % i == 0) {
      bool prt = 0;
      while (val % i == 0) {
        prt ^= 1;
        val /= i;
      }
      if (prt) ret.emplace_back(i);
    }
  if (val > 1) ret.emplace_back(val);
  return ret;
}
int n;
vector<int> a;
vector<vector<int> > com, ele;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  a.assign(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    com.emplace_back(simplify(a[i]));
  }
  sort((com).begin(), (com).end());
  com.erase(unique((com).begin(), (com).end()), com.end());
  ele.assign(((int)(com).size()), {});
  for (int i = 0; i < n; ++i) {
    ele[(int)(lower_bound((com).begin(), (com).end(), simplify(a[i])) -
              com.begin())]
        .emplace_back(i);
  }
  f.assign(1, Num(1));
  int prvGroup = 0;
  for (auto group : ele) {
    vector<vector<Num> > g(((int)(group).size()),
                           vector<Num>(((int)(f).size()), Num()));
    g[0] = f;
    for (int curGroup = 0; curGroup < ((int)(group).size()); ++curGroup) {
      vector<vector<Num> > nG(((int)(g).size()),
                              vector<Num>(((int)(g.back()).size()), Num()));
      for (int i = 0; i < ((int)(g).size()); ++i) {
        for (int j = 0; j < ((int)(g[i]).size()); ++j)
          if (g[i][j].a) {
            if (j) nG[i][j - 1] += g[i][j] * Num(j);
            if (i + 1 < ((int)(g).size()))
              nG[i + 1][j] += g[i][j] * Num((curGroup << 1) - i);
            nG[i][j] += g[i][j] * Num(curGroup + prvGroup + 1 - j -
                                      ((curGroup << 1) - i));
          }
      }
      g.swap(nG);
    }
    prvGroup += ((int)(group).size());
    f.assign(prvGroup, Num());
    for (int i = 0; i < ((int)(g).size()); ++i) {
      for (int j = 0; j < ((int)(g[i]).size()); ++j) f[i + j] += g[i][j];
    }
  }
  cout << f[0].a << '\n';
  cout.flush();
  return 0;
}

```