source_code: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.io.PrintStream;
  import java.util.Arrays;
  import java.io.IOException;
  import java.io.UncheckedIOException;
  import java.io.Closeable;
  import java.io.Writer;
  import java.io.OutputStreamWriter;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
      public static void main(String[] args) throws Exception {
          Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
          thread.start();
          thread.join();
      }
  
      static class TaskAdapter implements Runnable {
          @Override
          public void run() {
              InputStream inputStream = System.in;
              OutputStream outputStream = System.out;
              FastInput in = new FastInput(inputStream);
              FastOutput out = new FastOutput(outputStream);
              COnTheBench solver = new COnTheBench();
              solver.solve(1, in, out);
              out.close();
          }
      }
  
      static class COnTheBench {
          Modular mod = new Modular(1e9 + 7);
          Factorial fact = new Factorial(1000, mod);
          Combination comb = new Combination(fact);
          Debug debug = new Debug(true);
  
          public int f(int i, int j) {
              int ans = mod.mul(fact.fact(i), comb.combination(i + j - 1 - j, j - 1));
              ans = mod.mul(ans, fact.invFact(j));
              return ans;
          }
  
          public void solve(int testNumber, FastInput in, FastOutput out) {
              int n = in.readInt();
              DSU dsu = new DSU(n);
              long[] a = new long[n];
              for (int i = 0; i < n; i++) {
                  a[i] = in.readInt();
              }
              for (int i = 0; i < n; i++) {
                  for (int j = 0; j < i; j++) {
                      if (square(a[j] * a[i])) {
                          dsu.merge(j, i);
                          break;
                      }
                  }
              }
  
              IntegerList list = new IntegerList();
              for (int i = 0; i < n; i++) {
                  if (dsu.find(i) == i) {
                      list.add(dsu.size[dsu.find(i)]);
                  }
              }
  
              int[] cnts = list.toArray();
              debug.debug("cnts", cnts);
              int m = cnts.length;
              int[][] dp = new int[m + 1][n + 1];
              dp[0][0] = 1;
              for (int i = 1; i <= m; i++) {
                  int way = cnts[i - 1];
                  for (int j = 0; j <= n; j++) {
                      dp[i][j] = 0;
                      for (int k = 1; k <= j && k <= way; k++) {
                          int contrib = mod.mul(f(way, k), dp[i - 1][j - k]);
                          dp[i][j] = mod.plus(dp[i][j], contrib);
                      }
                  }
              }
              debug.debug("dp", dp);
  
              int ans = 0;
              for (int i = 0; i <= n; i++) {
                  int local = mod.mul(dp[m][i], fact.fact(i));
                  if ((n - i) % 2 == 1) {
                      local = mod.valueOf(-local);
                  }
                  ans = mod.plus(ans, local);
              }
  
              out.println(ans);
          }
  
          public boolean square(long x) {
              long l = 1;
              long r = (long) 1e9;
              while (l < r) {
                  long m = (l + r) / 2;
                  if (m * m < x) {
                      l = m + 1;
                  } else {
                      r = m;
                  }
              }
              return l * l == x;
          }
  
      }
  
      static class IntegerList implements Cloneable {
          private int size;
          private int cap;
          private int[] data;
          private static final int[] EMPTY = new int[0];
  
          public IntegerList(int cap) {
              this.cap = cap;
              if (cap == 0) {
                  data = EMPTY;
              } else {
                  data = new int[cap];
              }
          }
  
          public IntegerList(IntegerList list) {
              this.size = list.size;
              this.cap = list.cap;
              this.data = Arrays.copyOf(list.data, size);
          }
  
          public IntegerList() {
              this(0);
          }
  
          public void ensureSpace(int req) {
              if (req > cap) {
                  while (cap < req) {
                      cap = Math.max(cap + 10, 2 * cap);
                  }
                  data = Arrays.copyOf(data, cap);
              }
          }
  
          public void add(int x) {
              ensureSpace(size + 1);
              data[size++] = x;
          }
  
          public void addAll(int[] x, int offset, int len) {
              ensureSpace(size + len);
              System.arraycopy(x, offset, data, size, len);
              size += len;
          }
  
          public void addAll(IntegerList list) {
              addAll(list.data, 0, list.size);
          }
  
          public int[] toArray() {
              return Arrays.copyOf(data, size);
          }
  
          public String toString() {
              return Arrays.toString(toArray());
          }
  
          public boolean equals(Object obj) {
              if (!(obj instanceof IntegerList)) {
                  return false;
              }
              IntegerList other = (IntegerList) obj;
              return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
          }
  
          public int hashCode() {
              int h = 1;
              for (int i = 0; i < size; i++) {
                  h = h * 31 + Integer.hashCode(data[i]);
              }
              return h;
          }
  
          public IntegerList clone() {
              IntegerList ans = new IntegerList();
              ans.addAll(this);
              return ans;
          }
  
      }
  
      static class Combination implements IntCombination {
          final Factorial factorial;
          final Modular modular;
  
          public Combination(Factorial factorial) {
              this.factorial = factorial;
              this.modular = factorial.getModular();
          }
  
          public Combination(int limit, Modular modular) {
              this(new Factorial(limit, modular));
          }
  
          public int combination(int m, int n) {
              if (n > m) {
                  return 0;
              }
              return modular.mul(modular.mul(factorial.fact(m), factorial.invFact(n)), factorial.invFact(m - n));
          }
  
      }
  
      static class FastInput {
          private final InputStream is;
          private byte[] buf = new byte[1 << 13];
          private int bufLen;
          private int bufOffset;
          private int next;
  
          public FastInput(InputStream is) {
              this.is = is;
          }
  
          private int read() {
              while (bufLen == bufOffset) {
                  bufOffset = 0;
                  try {
                      bufLen = is.read(buf);
                  } catch (IOException e) {
                      bufLen = -1;
                  }
                  if (bufLen == -1) {
                      return -1;
                  }
              }
              return buf[bufOffset++];
          }
  
          public void skipBlank() {
              while (next >= 0 && next <= 32) {
                  next = read();
              }
          }
  
          public int readInt() {
              int sign = 1;
  
              skipBlank();
              if (next == '+' || next == '-') {
                  sign = next == '+' ? 1 : -1;
                  next = read();
              }
  
              int val = 0;
              if (sign == 1) {
                  while (next >= '0' && next <= '9') {
                      val = val * 10 + next - '0';
                      next = read();
                  }
              } else {
                  while (next >= '0' && next <= '9') {
                      val = val * 10 - next + '0';
                      next = read();
                  }
              }
  
              return val;
          }
  
      }
  
      static interface IntCombination {
      }
  
      static class FastOutput implements AutoCloseable, Closeable, Appendable {
          private StringBuilder cache = new StringBuilder(10 << 20);
          private final Writer os;
  
          public FastOutput append(CharSequence csq) {
              cache.append(csq);
              return this;
          }
  
          public FastOutput append(CharSequence csq, int start, int end) {
              cache.append(csq, start, end);
              return this;
          }
  
          public FastOutput(Writer os) {
              this.os = os;
          }
  
          public FastOutput(OutputStream os) {
              this(new OutputStreamWriter(os));
          }
  
          public FastOutput append(char c) {
              cache.append(c);
              return this;
          }
  
          public FastOutput append(int c) {
              cache.append(c);
              return this;
          }
  
          public FastOutput println(int c) {
              return append(c).println();
          }
  
          public FastOutput println() {
              cache.append(System.lineSeparator());
              return this;
          }
  
          public FastOutput flush() {
              try {
                  os.append(cache);
                  os.flush();
                  cache.setLength(0);
              } catch (IOException e) {
                  throw new UncheckedIOException(e);
              }
              return this;
          }
  
          public void close() {
              flush();
              try {
                  os.close();
              } catch (IOException e) {
                  throw new UncheckedIOException(e);
              }
          }
  
          public String toString() {
              return cache.toString();
          }
  
      }
  
      static class InverseNumber {
          int[] inv;
  
          public InverseNumber(int[] inv, int limit, Modular modular) {
              this.inv = inv;
              inv[1] = 1;
              int p = modular.getMod();
              for (int i = 2; i <= limit; i++) {
                  int k = p / i;
                  int r = p % i;
                  inv[i] = modular.mul(-k, inv[r]);
              }
          }
  
          public InverseNumber(int limit, Modular modular) {
              this(new int[limit + 1], limit, modular);
          }
  
      }
  
      static class Debug {
          private boolean offline;
          private PrintStream out = System.err;
          static int[] empty = new int[0];
  
          public Debug(boolean enable) {
              offline = enable && System.getSecurityManager() == null;
          }
  
          public Debug debug(String name, Object x) {
              return debug(name, x, empty);
          }
  
          public Debug debug(String name, Object x, int... indexes) {
              if (offline) {
                  if (x == null || !x.getClass().isArray()) {
                      out.append(name);
                      for (int i : indexes) {
                          out.printf("[%d]", i);
                      }
                      out.append("=").append("" + x);
                      out.println();
                  } else {
                      indexes = Arrays.copyOf(indexes, indexes.length + 1);
                      if (x instanceof byte[]) {
                          byte[] arr = (byte[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof short[]) {
                          short[] arr = (short[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof boolean[]) {
                          boolean[] arr = (boolean[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof char[]) {
                          char[] arr = (char[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof int[]) {
                          int[] arr = (int[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof float[]) {
                          float[] arr = (float[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof double[]) {
                          double[] arr = (double[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else if (x instanceof long[]) {
                          long[] arr = (long[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      } else {
                          Object[] arr = (Object[]) x;
                          for (int i = 0; i < arr.length; i++) {
                              indexes[indexes.length - 1] = i;
                              debug(name, arr[i], indexes);
                          }
                      }
                  }
              }
              return this;
          }
  
      }
  
      static class Factorial {
          int[] fact;
          int[] inv;
          Modular modular;
  
          public Modular getModular() {
              return modular;
          }
  
          public Factorial(int[] fact, int[] inv, InverseNumber in, int limit, Modular modular) {
              this.modular = modular;
              this.fact = fact;
              this.inv = inv;
              fact[0] = inv[0] = 1;
              for (int i = 1; i <= limit; i++) {
                  fact[i] = modular.mul(fact[i - 1], i);
                  inv[i] = modular.mul(inv[i - 1], in.inv[i]);
              }
          }
  
          public Factorial(int limit, Modular modular) {
              this(new int[limit + 1], new int[limit + 1], new InverseNumber(limit, modular), limit, modular);
          }
  
          public int fact(int n) {
              return fact[n];
          }
  
          public int invFact(int n) {
              return inv[n];
          }
  
      }
  
      static class DSU {
          protected int[] p;
          protected int[] rank;
          int[] size;
  
          public DSU(int n) {
              p = new int[n];
              rank = new int[n];
              size = new int[n];
              reset();
          }
  
          public final void reset() {
              for (int i = 0; i < p.length; i++) {
                  p[i] = i;
                  rank[i] = 0;
                  size[i] = 1;
              }
          }
  
          public final int find(int a) {
              if (p[a] == p[p[a]]) {
                  return p[a];
              }
              return p[a] = find(p[a]);
          }
  
          public final void merge(int a, int b) {
              a = find(a);
              b = find(b);
              if (a == b) {
                  return;
              }
              if (rank[a] == rank[b]) {
                  rank[a]++;
              }
  
              if (rank[a] < rank[b]) {
                  int tmp = a;
                  a = b;
                  b = tmp;
              }
  
              size[a] += size[b];
              p[b] = a;
          }
  
      }
  
      static class Modular {
          int m;
  
          public int getMod() {
              return m;
          }
  
          public Modular(int m) {
              this.m = m;
          }
  
          public Modular(long m) {
              this.m = (int) m;
              if (this.m != m) {
                  throw new IllegalArgumentException();
              }
          }
  
          public Modular(double m) {
              this.m = (int) m;
              if (this.m != m) {
                  throw new IllegalArgumentException();
              }
          }
  
          public int valueOf(int x) {
              x %= m;
              if (x < 0) {
                  x += m;
              }
              return x;
          }
  
          public int valueOf(long x) {
              x %= m;
              if (x < 0) {
                  x += m;
              }
              return (int) x;
          }
  
          public int mul(int x, int y) {
              return valueOf((long) x * y);
          }
  
          public int plus(int x, int y) {
              return valueOf(x + y);
          }
  
          public String toString() {
              return "mod " + m;
          }
  
      }
  
      static class SequenceUtils {
          public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
              if ((ar - al) != (br - bl)) {
                  return false;
              }
              for (int i = al, j = bl; i <= ar; i++, j++) {
                  if (a[i] != b[j]) {
                      return false;
                  }
              }
              return true;
          }
  
      }
  }
  
  