#include <bits/stdc++.h>
using namespace std;
struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c;
    bool flag = false;
    x = 0;
    while (~c && !isdigit(c = getchar()) && c != '-')
      ;
    c == '-' && (flag = true, c = getchar());
    if (!~c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~c && !(isprint(c = getchar()) && c != ' '))
      ;
    return ~c;
  }
  inline long long read(char s[]) {
    char c;
    long long len = 0;
    while (~c && !(isprint(c = getchar()) && c != ' '))
      ;
    if (!~c) return 0;
    while (isprint(c) && c != ' ') s[len++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    long long pos = 0;
    while (s[pos] != '\0') putchar(s[pos++]);
  }
} io;
struct Solver {
 private:
  static const long long N = 400;
  static const long long MOD = 1000000007;
  long long n, a[N + 1], top, cnt[N + 1], fact[N + 1];
  ;
  long long c[N + 1][N + 1], f[N + 1][N + 1];
  void input() {
    io.read(n);
    for (long long i = 1; i <= n; ++i) io.read(a[i]);
  }
  void init() {
    for (long long i = 1; i <= n; ++i)
      for (long long j = 2; j * j <= a[i]; ++j)
        while (!(a[i] % (j * j))) a[i] /= j * j;
    sort(a + 1, a + n + 1);
    for (long long i = 0; i <= N; ++i) c[i][0] = c[i][i] = 1;
    for (long long i = 2; i <= N; ++i)
      for (long long j = 1; j < i; ++j)
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
    fact[1] = 1;
    for (long long i = 2; i <= N; ++i) fact[i] = fact[i - 1] * i % MOD;
  }
  void process() {
    for (long long i = 1; i <= n; ++i)
      if (a[i] != a[i - 1])
        cnt[++top] = 1;
      else
        ++cnt[top];
    f[1][cnt[1] - 1] = 1;
    long long sum = cnt[1];
    for (long long i = 1; i < top; sum += cnt[++i])
      for (long long j = 0; j < sum; ++j) {
        if (!f[i][j]) continue;
        for (long long k = 0; k < cnt[i + 1]; ++k)
          for (long long l = 0; l <= min(k + 1, j); ++l) {
            long long tmp = f[i][j] * c[cnt[i + 1] - 1][k] % MOD * c[j][l] %
                            MOD * c[sum + 1 - j][k + 1 - l];
            (f[i + 1][j + cnt[i + 1] - 1 - k - l] += tmp) %= MOD;
          }
      }
    long long ans = f[top][0];
    for (long long i = 1; i <= top; ++i) (ans *= fact[cnt[i]]) %= MOD;
    io.write(ans), putchar('\n');
  }

 public:
  void solve() { input(), init(), process(); }
} solver;
signed main() {
  solver.solve();
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c;
    bool flag = false;
    x = 0;
    while (~c && !isdigit(c = getchar()) && c != '-')
      ;
    c == '-' && (flag = true, c = getchar());
    if (!~c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~c && !(isprint(c = getchar()) && c != ' '))
      ;
    return ~c;
  }
  inline long long read(char s[]) {
    char c;
    long long len = 0;
    while (~c && !(isprint(c = getchar()) && c != ' '))
      ;
    if (!~c) return 0;
    while (isprint(c) && c != ' ') s[len++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char s[]) {
    long long pos = 0;
    while (s[pos] != '\0') putchar(s[pos++]);
  }
} io;
struct Solver {
 private:
  static const long long N = 400;
  static const long long MOD = 1000000007;
  long long n, a[N + 1], top, cnt[N + 1], fact[N + 1];
  ;
  long long c[N + 1][N + 1], f[N + 1][N + 1];
  void input() {
    io.read(n);
    for (long long i = 1; i <= n; ++i) io.read(a[i]);
  }
  void init() {
    for (long long i = 1; i <= n; ++i)
      for (long long j = 2; j * j <= a[i]; ++j)
        while (!(a[i] % (j * j))) a[i] /= j * j;
    sort(a + 1, a + n + 1);
    for (long long i = 0; i <= N; ++i) c[i][0] = c[i][i] = 1;
    for (long long i = 2; i <= N; ++i)
      for (long long j = 1; j < i; ++j)
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
    fact[1] = 1;
    for (long long i = 2; i <= N; ++i) fact[i] = fact[i - 1] * i % MOD;
  }
  void process() {
    for (long long i = 1; i <= n; ++i)
      if (a[i] != a[i - 1])
        cnt[++top] = 1;
      else
        ++cnt[top];
    f[1][cnt[1] - 1] = 1;
    long long sum = cnt[1];
    for (long long i = 1; i < top; sum += cnt[++i])
      for (long long j = 0; j < sum; ++j) {
        if (!f[i][j]) continue;
        for (long long k = 0; k < cnt[i + 1]; ++k)
          for (long long l = 0; l <= min(k + 1, j); ++l) {
            long long tmp = f[i][j] * c[cnt[i + 1] - 1][k] % MOD * c[j][l] %
                            MOD * c[sum + 1 - j][k + 1 - l];
            (f[i + 1][j + cnt[i + 1] - 1 - k - l] += tmp) %= MOD;
          }
      }
    long long ans = f[top][0];
    for (long long i = 1; i <= top; ++i) (ans *= fact[cnt[i]]) %= MOD;
    io.write(ans), putchar('\n');
  }

 public:
  void solve() { input(), init(), process(); }
} solver;
signed main() {
  solver.solve();
  return 0;
}

```