#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T &x) {
  x = 0;
  char c = getchar();
  int flag = 0;
  while (c < '0' || c > '9') flag |= (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
template <class T>
T _max(T a, T b) {
  return a > b ? a : b;
}
template <class T>
T _min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
bool checkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int N = 605, mod = 1000000000 + 7;
int Add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
int Sub(int a, int b) {
  a -= b;
  return a >= 0 ? a : a + mod;
}
int Mul(int a, int b) { return 1LL * a * b % mod; }
void add(int &a, int b) { a = Add(a, b); }
void sub(int &a, int b) { a = Sub(a, b); }
void mul(int &a, int b) { a = Mul(a, b); }
int qpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) mul(ans, a);
    mul(a, a);
    b >>= 1;
  }
  return ans;
}
int n, a[N], fac[N], inv_fac[N], f[N], g[N], tmp[N];
int top = 0, S[N], near = 0;
int adjust(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      while (x % (i * i) == 0) {
        x /= i;
        x /= i;
      }
    }
  }
  return x;
}
void init() {
  read(n);
  for (int i = 1, x; i <= n; ++i) {
    read(x);
    a[i] = adjust(x);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) {
    if (a[i] != a[i - 1])
      S[++top] = 1;
    else
      S[top]++;
  }
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = Mul(fac[i - 1], i);
  }
  inv_fac[n] = qpow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; --i) {
    inv_fac[i] = Mul(inv_fac[i + 1], i + 1);
  }
}
void sft(int *f, int *g, int idx) {
  for (int i = 0; i <= near + S[idx] - 1; ++i) tmp[i] = 0;
  for (int i = 0; i <= near; ++i) {
    for (int j = 0; j <= S[idx] - 1; ++j) {
      add(tmp[i + j], Mul(f[i], g[j]));
    }
  }
  for (int i = 0; i <= near + S[idx] - 1; ++i) {
    f[i] = tmp[i];
  }
}
void solve() {
  f[0] = 1;
  for (int i = 1; i <= top; ++i) {
    int coef = 1;
    for (int q = 0; q <= S[i]; ++q) {
      g[q] = Mul(coef, inv_fac[q]);
      mul(coef, Mul(S[i] - q, S[i] - q - 1));
    }
    sft(f, g, i);
    near += S[i] - 1;
  }
  int ans = 0;
  for (int i = 0; i <= near; ++i) {
    mul(f[i], fac[n - i]);
    if (i % 2 == 0)
      add(ans, f[i]);
    else
      sub(ans, f[i]);
  }
  printf("%d\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

### Prompt

Please create a solution in Cpp 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;
template <class T>
void read(T &x) {
  x = 0;
  char c = getchar();
  int flag = 0;
  while (c < '0' || c > '9') flag |= (c == '-'), c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
template <class T>
T _max(T a, T b) {
  return a > b ? a : b;
}
template <class T>
T _min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
bool checkmax(T &a, T b) {
  return b > a ? a = b, 1 : 0;
}
template <class T>
bool checkmin(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int N = 605, mod = 1000000000 + 7;
int Add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
int Sub(int a, int b) {
  a -= b;
  return a >= 0 ? a : a + mod;
}
int Mul(int a, int b) { return 1LL * a * b % mod; }
void add(int &a, int b) { a = Add(a, b); }
void sub(int &a, int b) { a = Sub(a, b); }
void mul(int &a, int b) { a = Mul(a, b); }
int qpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) mul(ans, a);
    mul(a, a);
    b >>= 1;
  }
  return ans;
}
int n, a[N], fac[N], inv_fac[N], f[N], g[N], tmp[N];
int top = 0, S[N], near = 0;
int adjust(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      while (x % (i * i) == 0) {
        x /= i;
        x /= i;
      }
    }
  }
  return x;
}
void init() {
  read(n);
  for (int i = 1, x; i <= n; ++i) {
    read(x);
    a[i] = adjust(x);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) {
    if (a[i] != a[i - 1])
      S[++top] = 1;
    else
      S[top]++;
  }
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = Mul(fac[i - 1], i);
  }
  inv_fac[n] = qpow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; --i) {
    inv_fac[i] = Mul(inv_fac[i + 1], i + 1);
  }
}
void sft(int *f, int *g, int idx) {
  for (int i = 0; i <= near + S[idx] - 1; ++i) tmp[i] = 0;
  for (int i = 0; i <= near; ++i) {
    for (int j = 0; j <= S[idx] - 1; ++j) {
      add(tmp[i + j], Mul(f[i], g[j]));
    }
  }
  for (int i = 0; i <= near + S[idx] - 1; ++i) {
    f[i] = tmp[i];
  }
}
void solve() {
  f[0] = 1;
  for (int i = 1; i <= top; ++i) {
    int coef = 1;
    for (int q = 0; q <= S[i]; ++q) {
      g[q] = Mul(coef, inv_fac[q]);
      mul(coef, Mul(S[i] - q, S[i] - q - 1));
    }
    sft(f, g, i);
    near += S[i] - 1;
  }
  int ans = 0;
  for (int i = 0; i <= near; ++i) {
    mul(f[i], fac[n - i]);
    if (i % 2 == 0)
      add(ans, f[i]);
    else
      sub(ans, f[i]);
  }
  printf("%d\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

```