#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  os << '[';
  for (unsigned int i = 0; i < a.size(); i++)
    os << a[i] << (i < a.size() - 1 ? ", " : "");
  os << ']';
  return os;
}
int read() {
  int x;
  cin >> x;
  return x;
}
int n;
vector<vector<int> > vec;
int f[305];
int c[605][605];
int dp[305][305];
const int mod = 1e9 + 7;
int C(int k, int n) {
  if (k > n || k < 0) return 0;
  return c[k][n];
}
int candy(int k, int n) { return C(n - 1, n + k - 1); }
int cal(int lev, int mustfil, int placed) {
  if (lev == vec.size()) {
    if (mustfil == 0) return 1;
    return 0;
  }
  int &ret = dp[lev][mustfil];
  if (ret != -1) return ret;
  ret = 0;
  int X = vec[lev].size();
  int A = mustfil;
  int B = placed + 1 - mustfil;
  for (int add = (int)0; add <= (int)X - 1; add++) {
    int tmp = 0;
    for (int dec = (int)max(0, X - add - B); dec <= (int)min(mustfil, X - add);
         dec++) {
      int inA = dec;
      int inB = X - add - dec;
      int wayinA = C(inA, A);
      int wayinB = C(inB, B);
      tmp = (tmp + 1LL * cal(lev + 1, mustfil + add - dec, placed + X) *
                       wayinA % mod * wayinB % mod) %
            mod;
    }
    tmp = 1LL * tmp * candy(add, X - add) % mod;
    ret = (ret + tmp) % mod;
  }
  ret = (1LL * ret * f[X]) % mod;
  return ret;
}
void prep() {
  for (int i = (int)0; i <= (int)600; i++) {
    for (int j = (int)i; j <= (int)600; j++) {
      if (i == 0) {
        c[0][j] = 1;
        continue;
      }
      if (i == 1) {
        c[1][j] = j;
        continue;
      }
      c[i][j] = (c[i][j - 1] + c[i - 1][j - 1]) % mod;
    }
  }
}
vector<int> a;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  prep();
  cin >> n;
  for (int i = (int)1; i <= (int)n; i++) {
    int t;
    cin >> t;
    a.push_back(t);
  }
  for (auto it : a) {
    bool ok = false;
    for (auto &curvec : vec) {
      long long X = 1LL * curvec.front() * it;
      int X2 = sqrt(X);
      if (1LL * X2 * X2 == X) {
        curvec.push_back(it);
        ok = true;
        break;
      }
    }
    if (ok) continue;
    vector<int> tmp = {it};
    vec.push_back(tmp);
  }
  f[0] = 1;
  for (int i = (int)1; i <= (int)n; i++) f[i] = 1LL * f[i - 1] * i % mod;
  memset(dp, -1, sizeof(dp));
  cout << cal(0, 0, 0) << '\n';
}

### 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;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
  return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
  os << '[';
  for (unsigned int i = 0; i < a.size(); i++)
    os << a[i] << (i < a.size() - 1 ? ", " : "");
  os << ']';
  return os;
}
int read() {
  int x;
  cin >> x;
  return x;
}
int n;
vector<vector<int> > vec;
int f[305];
int c[605][605];
int dp[305][305];
const int mod = 1e9 + 7;
int C(int k, int n) {
  if (k > n || k < 0) return 0;
  return c[k][n];
}
int candy(int k, int n) { return C(n - 1, n + k - 1); }
int cal(int lev, int mustfil, int placed) {
  if (lev == vec.size()) {
    if (mustfil == 0) return 1;
    return 0;
  }
  int &ret = dp[lev][mustfil];
  if (ret != -1) return ret;
  ret = 0;
  int X = vec[lev].size();
  int A = mustfil;
  int B = placed + 1 - mustfil;
  for (int add = (int)0; add <= (int)X - 1; add++) {
    int tmp = 0;
    for (int dec = (int)max(0, X - add - B); dec <= (int)min(mustfil, X - add);
         dec++) {
      int inA = dec;
      int inB = X - add - dec;
      int wayinA = C(inA, A);
      int wayinB = C(inB, B);
      tmp = (tmp + 1LL * cal(lev + 1, mustfil + add - dec, placed + X) *
                       wayinA % mod * wayinB % mod) %
            mod;
    }
    tmp = 1LL * tmp * candy(add, X - add) % mod;
    ret = (ret + tmp) % mod;
  }
  ret = (1LL * ret * f[X]) % mod;
  return ret;
}
void prep() {
  for (int i = (int)0; i <= (int)600; i++) {
    for (int j = (int)i; j <= (int)600; j++) {
      if (i == 0) {
        c[0][j] = 1;
        continue;
      }
      if (i == 1) {
        c[1][j] = j;
        continue;
      }
      c[i][j] = (c[i][j - 1] + c[i - 1][j - 1]) % mod;
    }
  }
}
vector<int> a;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  prep();
  cin >> n;
  for (int i = (int)1; i <= (int)n; i++) {
    int t;
    cin >> t;
    a.push_back(t);
  }
  for (auto it : a) {
    bool ok = false;
    for (auto &curvec : vec) {
      long long X = 1LL * curvec.front() * it;
      int X2 = sqrt(X);
      if (1LL * X2 * X2 == X) {
        curvec.push_back(it);
        ok = true;
        break;
      }
    }
    if (ok) continue;
    vector<int> tmp = {it};
    vec.push_back(tmp);
  }
  f[0] = 1;
  for (int i = (int)1; i <= (int)n; i++) f[i] = 1LL * f[i - 1] * i % mod;
  memset(dp, -1, sizeof(dp));
  cout << cal(0, 0, 0) << '\n';
}

```