#include <bits/stdc++.h>
using namespace std;
long long n, x, mod = 1e9 + 7, b[333], c[333][333], cnt, dp[333][333], i, j, k,
                l, ans, all;
map<long long, long long> mp;
int main() {
  ios::sync_with_stdio(false);
  ;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> x;
    for (j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) {
        x /= j * j;
      }
    }
    mp[x]++;
  }
  for (i = 0; i <= n; i++) {
    c[i][0] = 1;
    for (j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
       it++) {
    b[cnt++] = it->second;
  }
  dp[0][0] = 1;
  long long all = 0;
  for (i = 0; i < cnt; i++) {
    for (j = 0; j <= all; j++) {
      if (dp[i][j] == 0) {
        continue;
      }
      for (k = 1; k <= min(b[i], all + 1); k++) {
        for (l = 0; l <= min(j, k); l++) {
          long long d = dp[i][j];
          d = (d * c[b[i] - 1][k - 1]) % mod;
          d = (d * c[j][l]) % mod;
          d = (d * c[all - j + 1][k - l]) % mod;
          dp[i + 1][j - l + b[i] - k] = (dp[i + 1][j - l + b[i] - k] + d) % mod;
        }
      }
    }
    all += b[i];
  }
  ans = dp[cnt][0];
  for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
       it++) {
    for (j = 1; j <= (it->second); j++) {
      ans = ans * j % mod;
    }
  }
  cout << ans;
  return 0;
}

### Prompt

Develop a solution in cpp 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;
long long n, x, mod = 1e9 + 7, b[333], c[333][333], cnt, dp[333][333], i, j, k,
                l, ans, all;
map<long long, long long> mp;
int main() {
  ios::sync_with_stdio(false);
  ;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> x;
    for (j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) {
        x /= j * j;
      }
    }
    mp[x]++;
  }
  for (i = 0; i <= n; i++) {
    c[i][0] = 1;
    for (j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
       it++) {
    b[cnt++] = it->second;
  }
  dp[0][0] = 1;
  long long all = 0;
  for (i = 0; i < cnt; i++) {
    for (j = 0; j <= all; j++) {
      if (dp[i][j] == 0) {
        continue;
      }
      for (k = 1; k <= min(b[i], all + 1); k++) {
        for (l = 0; l <= min(j, k); l++) {
          long long d = dp[i][j];
          d = (d * c[b[i] - 1][k - 1]) % mod;
          d = (d * c[j][l]) % mod;
          d = (d * c[all - j + 1][k - l]) % mod;
          dp[i + 1][j - l + b[i] - k] = (dp[i + 1][j - l + b[i] - k] + d) % mod;
        }
      }
    }
    all += b[i];
  }
  ans = dp[cnt][0];
  for (map<long long, long long>::iterator it = mp.begin(); it != mp.end();
       it++) {
    for (j = 1; j <= (it->second); j++) {
      ans = ans * j % mod;
    }
  }
  cout << ans;
  return 0;
}

```