#include <bits/stdc++.h>
using namespace std;
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
long long fact[2000001];
long long inv[2000001];
void factorial() {
  long long i;
  fact[0] = 1;
  inv[0] = power(fact[0], 1000000007 - 2);
  for (i = 1; i <= 2000000; i++) {
    fact[i] = (i * fact[i - 1]) % 1000000007;
    inv[i] = power(fact[i], 1000000007 - 2);
  }
}
long long ncr(long long x, long long y) {
  if (x < y or x < 0 or y < 0) return 0;
  long long temp = fact[x];
  temp = (temp * inv[y]) % 1000000007;
  temp = (temp * inv[x - y]) % 1000000007;
  return temp;
}
pair<long long, long long> ar[1000001];
void ini() {
  long long i;
  for (i = 0; i <= 1000000; i++) ar[i].first = i, ar[i].second = 1;
}
long long root(long long x) {
  if (ar[x].first != x) ar[x].first = root(ar[x].first);
  return ar[x].first;
}
void uni(long long x, long long y) {
  long long p = root(x);
  long long q = root(y);
  if (ar[p].second > ar[q].second) {
    ar[q].first = ar[p].first;
    ar[p].second += ar[q].second;
  } else {
    ar[p].first = ar[q].first;
    ar[q].second += ar[p].second;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  factorial();
  ini();
  int t = 1;
  while (t--) {
    long long n;
    cin >> n;
    long long temp[n];
    long long i, j, k, p;
    for (i = 0; i < n; i++) cin >> temp[i];
    for (i = 0; i < n; i++) {
      for (j = i + 1; j < n; j++) {
        long long low = 1, high = 1e9;
        long long ans = -1;
        while (low <= high) {
          long long mid = (low + high) / 2;
          if (mid * mid == temp[i] * temp[j]) {
            ans = mid;
            break;
          }
          if (mid * mid > temp[i] * temp[j])
            high = mid - 1;
          else
            low = mid + 1;
        }
        if (ans != -1 and root(i) != root(j)) uni(i, j);
      }
    }
    set<long long> lol;
    for (i = 0; i < n; i++) lol.insert(root(i));
    long long arr[lol.size()];
    i = 0;
    for (auto v : lol) arr[i++] = ar[v].second;
    n = lol.size();
    long long dp[n][305];
    long long pref[n];
    pref[0] = arr[0];
    for (i = 1; i < n; i++) pref[i] = pref[i - 1] + arr[i];
    for (j = 0; j < n; j++)
      for (i = 0; i <= 304; i++) dp[j][i] = 0;
    dp[0][arr[0] - 1] = fact[arr[0]];
    for (i = 1; i < n; i++) {
      for (j = 0; j < pref[i - 1]; j++) {
        for (k = 1; k <= min(pref[i - 1] + 1, arr[i]); k++) {
          for (p = 0; p <= min(j, k); p++) {
            long long bad = p;
            long long good = k - bad;
            long long total_good = pref[i - 1] + 1 - j;
            long long total_bad = j;
            long long new_bad = total_bad - p + arr[i] - k;
            dp[i][new_bad] += dp[i - 1][j] * ncr(total_bad, bad) % 1000000007 *
                              ncr(total_good, good) % 1000000007 *
                              ncr(arr[i] - 1, k - 1) % 1000000007 *
                              fact[arr[i]] % 1000000007;
            dp[i][new_bad] %= 1000000007;
          }
        }
      }
    }
    cout << dp[n - 1][0] << "\n";
  }
}

### Prompt

Your task is to create a cpp solution 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;
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
long long fact[2000001];
long long inv[2000001];
void factorial() {
  long long i;
  fact[0] = 1;
  inv[0] = power(fact[0], 1000000007 - 2);
  for (i = 1; i <= 2000000; i++) {
    fact[i] = (i * fact[i - 1]) % 1000000007;
    inv[i] = power(fact[i], 1000000007 - 2);
  }
}
long long ncr(long long x, long long y) {
  if (x < y or x < 0 or y < 0) return 0;
  long long temp = fact[x];
  temp = (temp * inv[y]) % 1000000007;
  temp = (temp * inv[x - y]) % 1000000007;
  return temp;
}
pair<long long, long long> ar[1000001];
void ini() {
  long long i;
  for (i = 0; i <= 1000000; i++) ar[i].first = i, ar[i].second = 1;
}
long long root(long long x) {
  if (ar[x].first != x) ar[x].first = root(ar[x].first);
  return ar[x].first;
}
void uni(long long x, long long y) {
  long long p = root(x);
  long long q = root(y);
  if (ar[p].second > ar[q].second) {
    ar[q].first = ar[p].first;
    ar[p].second += ar[q].second;
  } else {
    ar[p].first = ar[q].first;
    ar[q].second += ar[p].second;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  factorial();
  ini();
  int t = 1;
  while (t--) {
    long long n;
    cin >> n;
    long long temp[n];
    long long i, j, k, p;
    for (i = 0; i < n; i++) cin >> temp[i];
    for (i = 0; i < n; i++) {
      for (j = i + 1; j < n; j++) {
        long long low = 1, high = 1e9;
        long long ans = -1;
        while (low <= high) {
          long long mid = (low + high) / 2;
          if (mid * mid == temp[i] * temp[j]) {
            ans = mid;
            break;
          }
          if (mid * mid > temp[i] * temp[j])
            high = mid - 1;
          else
            low = mid + 1;
        }
        if (ans != -1 and root(i) != root(j)) uni(i, j);
      }
    }
    set<long long> lol;
    for (i = 0; i < n; i++) lol.insert(root(i));
    long long arr[lol.size()];
    i = 0;
    for (auto v : lol) arr[i++] = ar[v].second;
    n = lol.size();
    long long dp[n][305];
    long long pref[n];
    pref[0] = arr[0];
    for (i = 1; i < n; i++) pref[i] = pref[i - 1] + arr[i];
    for (j = 0; j < n; j++)
      for (i = 0; i <= 304; i++) dp[j][i] = 0;
    dp[0][arr[0] - 1] = fact[arr[0]];
    for (i = 1; i < n; i++) {
      for (j = 0; j < pref[i - 1]; j++) {
        for (k = 1; k <= min(pref[i - 1] + 1, arr[i]); k++) {
          for (p = 0; p <= min(j, k); p++) {
            long long bad = p;
            long long good = k - bad;
            long long total_good = pref[i - 1] + 1 - j;
            long long total_bad = j;
            long long new_bad = total_bad - p + arr[i] - k;
            dp[i][new_bad] += dp[i - 1][j] * ncr(total_bad, bad) % 1000000007 *
                              ncr(total_good, good) % 1000000007 *
                              ncr(arr[i] - 1, k - 1) % 1000000007 *
                              fact[arr[i]] % 1000000007;
            dp[i][new_bad] %= 1000000007;
          }
        }
      }
    }
    cout << dp[n - 1][0] << "\n";
  }
}

```