### 问题描述

在古老的大陆上，有一位年轻的勇士小蓝，他背负着保护人民的使命，踏上了冒险之旅。大陆上隐藏着无数的古老遗迹和神秘力量，其中之一是传说中的"铭记传承"。

据传闻，"铭记传承"是一种古老的魔法，它可以使勇士们获得强大的力量。这种魔法与一系列神秘数字相关联，而这些数字则代表着一段序列。勇士们需要通过解谜，找到满足特定条件的序列排列，才能触发"铭记传承"的魔法力量。

小蓝听闻了这个传说，决定接受挑战，寻找"铭记传承"的力量。他获得了一段序列 $a$，长度为 $n$，但这段序列的具体含义仍然是个谜。

小蓝知道，他需要找到满足以下条件的排列 $p$ 才能激活"铭记传承"的魔法力量：

对于 $2 \le i \le n$，必须存在 $a_{p_{i-1}} \times a_{p_i}$ 是一个完全平方数。

小蓝需要你的帮助，计算一共有多少种满足条件的排列 $p$。由于结果可能很大，你需要将答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$（$1 \le n \le 1000$），表示序列 $a$ 的长度。

第二行输入 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示序列 $a$ 中的元素。

输出格式

输出仅一行，为满足条件的排列 $p$ 的总数对 $998244353$ 取模后的结果。

样例输入

3
1 4 4

样例输出

6