#include <bits/stdc++.h>
const int MOD = 1000000007;
const int maxn = 333;
using LL = long long;
class TaskC {
  int n;
  std::map<int, int> nums;
  std::vector<int> prime;
  LL dp[maxn][maxn];
  LL fac[maxn];

 private:
  void generate_prime(int n) {
    std::vector<bool> isNotPrime((unsigned long)n, false);
    for (int i = 2; i < n; i++) {
      if (!isNotPrime[i]) {
        prime.push_back(i);
      }
      for (int j = 0; j < prime.size() && i * prime[j] < n; j++) {
        isNotPrime[i * prime[j]] = true;
        if (!(i % prime[j])) {
          break;
        }
      }
    }
  }
  void parse(int x) {
    std::map<int, int> cnt;
    for (auto p : prime) {
      if (x % p == 0) {
        int m = 0;
        while (x % p == 0) {
          x /= p;
          m++;
        }
        cnt[p] = m;
      }
    }
    if (x != 1) {
      cnt[x] += 1;
    }
    int res = 1;
    for (auto p : cnt) {
      if (p.second % 2 == 1) {
        res *= p.first;
      }
    }
    if (res == 1) {
      res = 0;
    }
    nums[res]++;
  }
  LL extend_gcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    LL d = extend_gcd(b, a % b, x, y);
    LL temp = x;
    x = y;
    y = temp - (a / b) * y;
    return d;
  }
  LL inv(LL x) {
    LL a, b;
    auto d = extend_gcd(x, MOD, a, b);
    if (d != 1) {
      printf(">>> %lld\n", x);
      assert(0);
    }
    return (a + MOD) % MOD;
  }
  void init() {
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) {
      fac[i] = fac[i - 1] * i % MOD;
    }
  }
  LL mul(LL a, LL b) {
    a %= MOD;
    b %= MOD;
    return a * b % MOD;
  }
  LL C(int n, int m) {
    if (m == 0) return 1;
    if (m > n) assert(0);
    return mul(mul(fac[n], inv(fac[m])), inv(fac[n - m]));
  }

 public:
  TaskC() {
    generate_prime(100000);
    init();
  }
  void solve(std::istream& in, std::ostream& out) {
    memset(dp, 0, sizeof dp);
    nums.clear();
    in >> n;
    for (int i = 0; i < n; i++) {
      int x;
      in >> x;
      parse(x);
    }
    int i = 0;
    int tot = 0;
    dp[0][0] = 1;
    for (auto p : nums) {
      i++;
      tot += p.second;
      for (int k = 1; k <= tot; k++) {
        int ed = std::min(p.second, k);
        for (int j = 1; j <= ed; j++) {
          if (k - j < 0) assert(0);
          dp[i][k] += mul(
              mul(mul(dp[i - 1][k - j], C(p.second - 1, j - 1)), fac[p.second]),
              inv(fac[j]));
          dp[i][k] %= MOD;
        }
      }
    }
    LL ans = 0;
    for (int k = tot; k >= 1; k--) {
      if ((tot - k) % 2 == 0) {
        ans += mul(dp[i][k], fac[k]);
      } else {
        ans -= mul(dp[i][k], fac[k]);
      }
      ans += MOD;
      ans %= MOD;
    }
    out << ans << std::endl;
  }
};
int main() {
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  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>
const int MOD = 1000000007;
const int maxn = 333;
using LL = long long;
class TaskC {
  int n;
  std::map<int, int> nums;
  std::vector<int> prime;
  LL dp[maxn][maxn];
  LL fac[maxn];

 private:
  void generate_prime(int n) {
    std::vector<bool> isNotPrime((unsigned long)n, false);
    for (int i = 2; i < n; i++) {
      if (!isNotPrime[i]) {
        prime.push_back(i);
      }
      for (int j = 0; j < prime.size() && i * prime[j] < n; j++) {
        isNotPrime[i * prime[j]] = true;
        if (!(i % prime[j])) {
          break;
        }
      }
    }
  }
  void parse(int x) {
    std::map<int, int> cnt;
    for (auto p : prime) {
      if (x % p == 0) {
        int m = 0;
        while (x % p == 0) {
          x /= p;
          m++;
        }
        cnt[p] = m;
      }
    }
    if (x != 1) {
      cnt[x] += 1;
    }
    int res = 1;
    for (auto p : cnt) {
      if (p.second % 2 == 1) {
        res *= p.first;
      }
    }
    if (res == 1) {
      res = 0;
    }
    nums[res]++;
  }
  LL extend_gcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    LL d = extend_gcd(b, a % b, x, y);
    LL temp = x;
    x = y;
    y = temp - (a / b) * y;
    return d;
  }
  LL inv(LL x) {
    LL a, b;
    auto d = extend_gcd(x, MOD, a, b);
    if (d != 1) {
      printf(">>> %lld\n", x);
      assert(0);
    }
    return (a + MOD) % MOD;
  }
  void init() {
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) {
      fac[i] = fac[i - 1] * i % MOD;
    }
  }
  LL mul(LL a, LL b) {
    a %= MOD;
    b %= MOD;
    return a * b % MOD;
  }
  LL C(int n, int m) {
    if (m == 0) return 1;
    if (m > n) assert(0);
    return mul(mul(fac[n], inv(fac[m])), inv(fac[n - m]));
  }

 public:
  TaskC() {
    generate_prime(100000);
    init();
  }
  void solve(std::istream& in, std::ostream& out) {
    memset(dp, 0, sizeof dp);
    nums.clear();
    in >> n;
    for (int i = 0; i < n; i++) {
      int x;
      in >> x;
      parse(x);
    }
    int i = 0;
    int tot = 0;
    dp[0][0] = 1;
    for (auto p : nums) {
      i++;
      tot += p.second;
      for (int k = 1; k <= tot; k++) {
        int ed = std::min(p.second, k);
        for (int j = 1; j <= ed; j++) {
          if (k - j < 0) assert(0);
          dp[i][k] += mul(
              mul(mul(dp[i - 1][k - j], C(p.second - 1, j - 1)), fac[p.second]),
              inv(fac[j]));
          dp[i][k] %= MOD;
        }
      }
    }
    LL ans = 0;
    for (int k = tot; k >= 1; k--) {
      if ((tot - k) % 2 == 0) {
        ans += mul(dp[i][k], fac[k]);
      } else {
        ans -= mul(dp[i][k], fac[k]);
      }
      ans += MOD;
      ans %= MOD;
    }
    out << ans << std::endl;
  }
};
int main() {
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

```