#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int n, a[305], C[305][305], cnt;
long long dp[305][305], fac[305], inv[305], ans;
map<vector<int>, int> mp;
inline long long fpow(long long x, int y = 1000000007 - 2) {
  if (y == 1) return x;
  long long t = fpow(x, y >> 1);
  (t *= t) %= 1000000007;
  if (y & 1) (t *= x) %= 1000000007;
  return t;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    vector<int> fact;
    int tmp = a[i];
    for (int j = 2; 1ll * j * j <= a[i]; j++) {
      if (tmp % j) continue;
      int ex = 0;
      while (tmp % j == 0) {
        tmp /= j;
        ex ^= 1;
      }
      if (ex) fact.push_back(j);
    }
    if (tmp > 1) fact.push_back(tmp);
    mp[fact]++;
  }
  for (int i = C[0][0] = fac[0] = inv[0] = 1; i <= n; i++) {
    fac[i] = (1ll * fac[i - 1] * i) % 1000000007;
    inv[i] = fpow(fac[i]);
    for (int j = C[i][0] = 1; j <= n; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % 1000000007;
  }
  dp[0][0] = 1;
  for (auto s : mp) {
    cnt++;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= min(i, s.second); j++)
        (dp[cnt][i] += 1ll * dp[cnt - 1][i - j] * fac[s.second] % 1000000007 *
                       inv[j] % 1000000007 * C[s.second - 1][j - 1] %
                       1000000007) %= 1000000007;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (n - i & 1)
      (ans += 1ll * (1000000007 - 1) * fac[i] % 1000000007 * dp[cnt][i] %
              1000000007) %= 1000000007;
    else
      (ans += 1ll * fac[i] * dp[cnt][i] % 1000000007) %= 1000000007;
  }
  cout << ans << endl;
  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 comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int n, a[305], C[305][305], cnt;
long long dp[305][305], fac[305], inv[305], ans;
map<vector<int>, int> mp;
inline long long fpow(long long x, int y = 1000000007 - 2) {
  if (y == 1) return x;
  long long t = fpow(x, y >> 1);
  (t *= t) %= 1000000007;
  if (y & 1) (t *= x) %= 1000000007;
  return t;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    vector<int> fact;
    int tmp = a[i];
    for (int j = 2; 1ll * j * j <= a[i]; j++) {
      if (tmp % j) continue;
      int ex = 0;
      while (tmp % j == 0) {
        tmp /= j;
        ex ^= 1;
      }
      if (ex) fact.push_back(j);
    }
    if (tmp > 1) fact.push_back(tmp);
    mp[fact]++;
  }
  for (int i = C[0][0] = fac[0] = inv[0] = 1; i <= n; i++) {
    fac[i] = (1ll * fac[i - 1] * i) % 1000000007;
    inv[i] = fpow(fac[i]);
    for (int j = C[i][0] = 1; j <= n; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % 1000000007;
  }
  dp[0][0] = 1;
  for (auto s : mp) {
    cnt++;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= min(i, s.second); j++)
        (dp[cnt][i] += 1ll * dp[cnt - 1][i - j] * fac[s.second] % 1000000007 *
                       inv[j] % 1000000007 * C[s.second - 1][j - 1] %
                       1000000007) %= 1000000007;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (n - i & 1)
      (ans += 1ll * (1000000007 - 1) * fac[i] % 1000000007 * dp[cnt][i] %
              1000000007) %= 1000000007;
    else
      (ans += 1ll * fac[i] * dp[cnt][i] % 1000000007) %= 1000000007;
  }
  cout << ans << endl;
  return 0;
}

```