#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
int n;
map<int, int> a;
int m;
vector<int> b;
long long dp[305][305];
long long fac[305];
long long ch[305][305];
void gch() {
  fac[0] = 1;
  ch[0][0] = 1;
  for (int i = (1); i <= (signed)(305 - 2); i++) {
    fac[i] = (fac[i - 1] * i) % 1000000007LL;
    for (int j = (0); j <= (signed)(i); j++) {
      ch[i][j] =
          (ch[i - 1][j] + (j == 0 ? 0 : ch[i - 1][j - 1])) % 1000000007LL;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  gch();
  cin >> n;
  for (int i = (1); i <= (signed)(n); i++) {
    int x;
    cin >> x;
    for (int j = 2; j * j <= x; ++j) {
      while (x % (j * j) == 0) {
        x /= (j * j);
      }
    }
    a[x]++;
  }
  for (auto u : a) {
    b.push_back(u.second);
  }
  m = b.size();
  dp[0][0] = 1;
  int amt = 0;
  for (int i = 0; i < (signed)(m); i++) {
    for (int j = (0); j <= (signed)(amt); j++) {
      for (int reg = (1); reg <= (signed)(min(b[i], amt + 1)); reg++)
        for (int yeet = (0); yeet <= (signed)(min(j, reg)); yeet++) {
          int nw = j + (b[i] - reg) - yeet;
          long long spl = (fac[b[i]] * ch[b[i] - 1][reg - 1]) % 1000000007LL;
          long long oth =
              (ch[j][yeet] * ch[amt + 1 - j][reg - yeet]) % 1000000007LL;
          long long fin = (spl * oth) % 1000000007LL;
          dp[i + 1][nw] = (dp[i + 1][nw] + (fin * dp[i][j])) % 1000000007LL;
        }
    }
    amt += b[i];
  }
  cout << dp[m][0] << "\n";
  return 0;
}

### 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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
int n;
map<int, int> a;
int m;
vector<int> b;
long long dp[305][305];
long long fac[305];
long long ch[305][305];
void gch() {
  fac[0] = 1;
  ch[0][0] = 1;
  for (int i = (1); i <= (signed)(305 - 2); i++) {
    fac[i] = (fac[i - 1] * i) % 1000000007LL;
    for (int j = (0); j <= (signed)(i); j++) {
      ch[i][j] =
          (ch[i - 1][j] + (j == 0 ? 0 : ch[i - 1][j - 1])) % 1000000007LL;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  gch();
  cin >> n;
  for (int i = (1); i <= (signed)(n); i++) {
    int x;
    cin >> x;
    for (int j = 2; j * j <= x; ++j) {
      while (x % (j * j) == 0) {
        x /= (j * j);
      }
    }
    a[x]++;
  }
  for (auto u : a) {
    b.push_back(u.second);
  }
  m = b.size();
  dp[0][0] = 1;
  int amt = 0;
  for (int i = 0; i < (signed)(m); i++) {
    for (int j = (0); j <= (signed)(amt); j++) {
      for (int reg = (1); reg <= (signed)(min(b[i], amt + 1)); reg++)
        for (int yeet = (0); yeet <= (signed)(min(j, reg)); yeet++) {
          int nw = j + (b[i] - reg) - yeet;
          long long spl = (fac[b[i]] * ch[b[i] - 1][reg - 1]) % 1000000007LL;
          long long oth =
              (ch[j][yeet] * ch[amt + 1 - j][reg - yeet]) % 1000000007LL;
          long long fin = (spl * oth) % 1000000007LL;
          dp[i + 1][nw] = (dp[i + 1][nw] + (fin * dp[i][j])) % 1000000007LL;
        }
    }
    amt += b[i];
  }
  cout << dp[m][0] << "\n";
  return 0;
}

```