#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
int mul(int a, int b) { return int(1LL * a * b % mod); }
int fexp(int b, int e = mod - 2) {
  int ans = 1;
  while (e) {
    if (e & 1) ans = mul(ans, b);
    b = mul(b, b);
    e /= 2;
  }
  return ans;
}
bool is_sqr(ll n) {
  ll x = (ll)sqrtl(n);
  while (x * x > n) x--;
  while (x * x < n) x++;
  return x * x == n;
}
const int N = 303;
int fact[2 * N], ifact[2 * N];
int C(int n, int k) {
  if (k > n) return 0;
  return mul(mul(fact[n], ifact[k]), ifact[n - k]);
}
int n, m;
int cnt[N], a[N];
int dp[N][N];
int ps[N];
int f(int i, int j) {
  if (i == n) return j == 1;
  int &ans = dp[i][j];
  if (~ans) return ans;
  ans = 0;
  for (int join = 0; join <= cnt[i] and join < j; join++) {
    int me = 1;
    me = mul(me, mul(fact[j], ifact[j - join]));
    me = mul(me, mul(fact[j - 1], ifact[j - join - 1]));
    me = mul(me, fact[cnt[i]]);
    me = mul(me, ifact[join]);
    me = mul(me, fact[2 * (j - join)]);
    for (int append = 0; append <= cnt[i] - join and append <= 2 * (j - join);
         append++) {
      int tmp = me;
      tmp = mul(tmp, ifact[2 * (j - join) - append]);
      tmp = mul(tmp, ifact[cnt[i] - join - append]);
      tmp = mul(tmp, ifact[append]);
      ans = add(ans, mul(tmp, f(i + 1, j - join + cnt[i] - join - append)));
    }
  }
  return ans;
}
int main() {
  memset(dp, -1, sizeof dp);
  fact[0] = 1;
  for (int i = 1; i < 2 * N; i++) fact[i] = mul(fact[i - 1], i);
  ifact[2 * N - 1] = fexp(fact[2 * N - 1]);
  for (int i = 2 * N - 2; i >= 0; i--) ifact[i] = mul(ifact[i + 1], i + 1);
  ps[0] = ps[1] = 1;
  for (int i = 2; i < N; i++) {
    ps[i] = mul(ps[i - 1], i * (i - 1));
  }
  scanf("%d", &n);
  m = n;
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    int j = 0;
    while (j < i and !is_sqr(1LL * a[i] * a[j])) {
      j++;
    }
    if (j < i) {
      cnt[j]++;
      n--, i--;
    } else {
      cnt[i] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
  }
  printf("%d\n", f(1, cnt[0]));
}

### Prompt

Please formulate 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;
using ll = long long;
const int mod = 1e9 + 7;
int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
int mul(int a, int b) { return int(1LL * a * b % mod); }
int fexp(int b, int e = mod - 2) {
  int ans = 1;
  while (e) {
    if (e & 1) ans = mul(ans, b);
    b = mul(b, b);
    e /= 2;
  }
  return ans;
}
bool is_sqr(ll n) {
  ll x = (ll)sqrtl(n);
  while (x * x > n) x--;
  while (x * x < n) x++;
  return x * x == n;
}
const int N = 303;
int fact[2 * N], ifact[2 * N];
int C(int n, int k) {
  if (k > n) return 0;
  return mul(mul(fact[n], ifact[k]), ifact[n - k]);
}
int n, m;
int cnt[N], a[N];
int dp[N][N];
int ps[N];
int f(int i, int j) {
  if (i == n) return j == 1;
  int &ans = dp[i][j];
  if (~ans) return ans;
  ans = 0;
  for (int join = 0; join <= cnt[i] and join < j; join++) {
    int me = 1;
    me = mul(me, mul(fact[j], ifact[j - join]));
    me = mul(me, mul(fact[j - 1], ifact[j - join - 1]));
    me = mul(me, fact[cnt[i]]);
    me = mul(me, ifact[join]);
    me = mul(me, fact[2 * (j - join)]);
    for (int append = 0; append <= cnt[i] - join and append <= 2 * (j - join);
         append++) {
      int tmp = me;
      tmp = mul(tmp, ifact[2 * (j - join) - append]);
      tmp = mul(tmp, ifact[cnt[i] - join - append]);
      tmp = mul(tmp, ifact[append]);
      ans = add(ans, mul(tmp, f(i + 1, j - join + cnt[i] - join - append)));
    }
  }
  return ans;
}
int main() {
  memset(dp, -1, sizeof dp);
  fact[0] = 1;
  for (int i = 1; i < 2 * N; i++) fact[i] = mul(fact[i - 1], i);
  ifact[2 * N - 1] = fexp(fact[2 * N - 1]);
  for (int i = 2 * N - 2; i >= 0; i--) ifact[i] = mul(ifact[i + 1], i + 1);
  ps[0] = ps[1] = 1;
  for (int i = 2; i < N; i++) {
    ps[i] = mul(ps[i - 1], i * (i - 1));
  }
  scanf("%d", &n);
  m = n;
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    int j = 0;
    while (j < i and !is_sqr(1LL * a[i] * a[j])) {
      j++;
    }
    if (j < i) {
      cnt[j]++;
      n--, i--;
    } else {
      cnt[i] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
  }
  printf("%d\n", f(1, cnt[0]));
}

```