#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const long long mod = 1e9 + 7;
long long dp[330][330];
long long c[330][330];
unordered_map<int, int> f;
void build(int x) {
  for (int i = 2; i * i <= x; i++) {
    while (x % (i * i) == 0) x /= (i * i);
  }
  f[x]++;
}
int num[330];
long long p[330];
void init() {
  for (int i = 0; i < 330; i++) c[i][i] = c[i][0] = 1;
  for (int i = 2; i < 330; i++) {
    for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  p[0] = 1;
  for (int i = 1; i < 330; i++) p[i] = p[i - 1] * i % mod;
}
long long C(int m, int n) {
  if (n > m) return 0;
  return c[m][n];
}
int main() {
  init();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    build(x);
  }
  int cnt = 1;
  for (auto elem : f) {
    num[cnt++] = elem.second;
  }
  memset(dp, 0, sizeof(dp));
  dp[1][num[1] - 1] = 1;
  int tot = num[1];
  for (int i = 2; i < cnt; i++) {
    for (int j = 0; j < tot; j++) {
      if (dp[i - 1][j] == 0) continue;
      for (int k = 1; k <= num[i]; k++) {
        for (int l = 0; l <= j; l++) {
          long long &ans = dp[i][j - l + num[i] - k];
          ans += dp[i - 1][j] * C(num[i] - 1, k - 1) % mod * C(j, l) % mod *
                 C(tot - j + 1, k - l) % mod;
          ans %= mod;
        }
      }
    }
    tot += num[i];
  }
  for (int i = 1; i < cnt; i++) {
    dp[cnt - 1][0] *= p[num[i]];
    dp[cnt - 1][0] %= mod;
  }
  cout << dp[cnt - 1][0] << endl;
}

### 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;
const int MAXN = 1e5 + 10;
const long long mod = 1e9 + 7;
long long dp[330][330];
long long c[330][330];
unordered_map<int, int> f;
void build(int x) {
  for (int i = 2; i * i <= x; i++) {
    while (x % (i * i) == 0) x /= (i * i);
  }
  f[x]++;
}
int num[330];
long long p[330];
void init() {
  for (int i = 0; i < 330; i++) c[i][i] = c[i][0] = 1;
  for (int i = 2; i < 330; i++) {
    for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  p[0] = 1;
  for (int i = 1; i < 330; i++) p[i] = p[i - 1] * i % mod;
}
long long C(int m, int n) {
  if (n > m) return 0;
  return c[m][n];
}
int main() {
  init();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    build(x);
  }
  int cnt = 1;
  for (auto elem : f) {
    num[cnt++] = elem.second;
  }
  memset(dp, 0, sizeof(dp));
  dp[1][num[1] - 1] = 1;
  int tot = num[1];
  for (int i = 2; i < cnt; i++) {
    for (int j = 0; j < tot; j++) {
      if (dp[i - 1][j] == 0) continue;
      for (int k = 1; k <= num[i]; k++) {
        for (int l = 0; l <= j; l++) {
          long long &ans = dp[i][j - l + num[i] - k];
          ans += dp[i - 1][j] * C(num[i] - 1, k - 1) % mod * C(j, l) % mod *
                 C(tot - j + 1, k - l) % mod;
          ans %= mod;
        }
      }
    }
    tot += num[i];
  }
  for (int i = 1; i < cnt; i++) {
    dp[cnt - 1][0] *= p[num[i]];
    dp[cnt - 1][0] %= mod;
  }
  cout << dp[cnt - 1][0] << endl;
}

```