#include <bits/stdc++.h>
using namespace std;
void SieveOfErat() {
  bool prime[1000001];
  memset(prime, true, sizeof(prime));
  for (long long vec = 2; vec * vec <= 1000000; vec++) {
    if (prime[vec] == true) {
      for (long long dd = vec * 2; dd <= 1000000; dd += vec) prime[dd] = false;
    }
  }
}
long long gcd(long long aa, long long y) {
  if (aa == 0) {
    return y;
  } else
    return gcd(aa % y, y);
}
long long dp[400][400];
long long c[400][400];
int a[400], v[400], n, tot, num, sum[400];
void pre() {
  c[0][0] = 1;
  for (int i = 1; i <= 300; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 1000000007;
  }
}
int cmp(int a, int b) { return a > b; }
int main() {
  pre();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (int j = 2; j <= sqrt(a[i]); j++)
      while (a[i] % (j * j) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++)
    if (a[i] != a[i - 1]) {
      if (i > 1) v[++tot] = num;
      num = 1;
    } else
      num++;
  v[++tot] = num;
  sort(v + 1, v + tot + 1, cmp);
  for (int i = 1; i <= tot; i++) sum[i] = sum[i - 1] + v[i];
  dp[1][v[1] - 1] = 1;
  for (int i = 1; i < tot; i++)
    for (int j = 0; j <= sum[i]; j++)
      if (dp[i][j])
        for (int k = 1; k <= v[i + 1]; k++) {
          long long num = c[v[i + 1] - 1][k - 1];
          for (int l = 0; l <= j; l++) {
            int nj = j - l + v[i + 1] - k;
            dp[i + 1][nj] += dp[i][j] * num % 1000000007 * c[j][l] %
                             1000000007 * c[sum[i] + 1 - j][k - l] % 1000000007;
            dp[i + 1][nj] %= 1000000007;
          }
        }
  for (int i = 1; i <= tot; i++) {
    long long num = 1;
    for (int j = 1; j <= v[i]; j++) num = num * j % 1000000007;
    dp[tot][0] = dp[tot][0] * num % 1000000007;
  }
  cout << dp[tot][0] << endl;
}

### Prompt

Please create a solution in cpp 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;
void SieveOfErat() {
  bool prime[1000001];
  memset(prime, true, sizeof(prime));
  for (long long vec = 2; vec * vec <= 1000000; vec++) {
    if (prime[vec] == true) {
      for (long long dd = vec * 2; dd <= 1000000; dd += vec) prime[dd] = false;
    }
  }
}
long long gcd(long long aa, long long y) {
  if (aa == 0) {
    return y;
  } else
    return gcd(aa % y, y);
}
long long dp[400][400];
long long c[400][400];
int a[400], v[400], n, tot, num, sum[400];
void pre() {
  c[0][0] = 1;
  for (int i = 1; i <= 300; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 1000000007;
  }
}
int cmp(int a, int b) { return a > b; }
int main() {
  pre();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    for (int j = 2; j <= sqrt(a[i]); j++)
      while (a[i] % (j * j) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++)
    if (a[i] != a[i - 1]) {
      if (i > 1) v[++tot] = num;
      num = 1;
    } else
      num++;
  v[++tot] = num;
  sort(v + 1, v + tot + 1, cmp);
  for (int i = 1; i <= tot; i++) sum[i] = sum[i - 1] + v[i];
  dp[1][v[1] - 1] = 1;
  for (int i = 1; i < tot; i++)
    for (int j = 0; j <= sum[i]; j++)
      if (dp[i][j])
        for (int k = 1; k <= v[i + 1]; k++) {
          long long num = c[v[i + 1] - 1][k - 1];
          for (int l = 0; l <= j; l++) {
            int nj = j - l + v[i + 1] - k;
            dp[i + 1][nj] += dp[i][j] * num % 1000000007 * c[j][l] %
                             1000000007 * c[sum[i] + 1 - j][k - l] % 1000000007;
            dp[i + 1][nj] %= 1000000007;
          }
        }
  for (int i = 1; i <= tot; i++) {
    long long num = 1;
    for (int j = 1; j <= v[i]; j++) num = num * j % 1000000007;
    dp[tot][0] = dp[tot][0] * num % 1000000007;
  }
  cout << dp[tot][0] << endl;
}

```