### 问题描述 在古老的大陆上，有一位年轻的勇士小蓝，他背负着保护人民的使命，踏上了冒险之旅。大陆上隐藏着无数的古老遗迹和神秘力量，其中之一是传说中的"铭记传承"。 据传闻，"铭记传承"是一种古老的魔法，它可以使勇士们获得强大的力量。这种魔法与一系列神秘数字相关联，而这些数字则代表着一段序列。勇士们需要通过解谜，找到满足特定条件的序列排列，才能触发"铭记传承"的魔法力量。 小蓝听闻了这个传说，决定接受挑战，寻找"铭记传承"的力量。他获得了一段序列 $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 ```