立冬之后，北京的空气就变得稀薄似的，每次呼吸都要十分谨慎，生怕多吸一口空气就会将自己冻伤似的，如此在风中战栗者不一而足。公交车站前，等待 819 路的人们排起长龙，或许是行将周末的缘故罢，他们的脸上似乎少了那么一丝疲倦。此刻，小 W 也只是看着夜空中那一轮月，看着熙熙攘攘走过的人们，抖动着身体以争取一丝温暖，静静地，等待着公交车的到来。

等车时，小 S 写给了小 W 共 $n$ 个正整数 $a_i$ ，此时，小 W 会先写出 $n$ 个正整数 $b_i$ ，使得对每一个 $i$ ，都有 $a_i$ 是 $b_i$ 的倍数，写完了之后，小 W 会再写出 $n$ 个正整数 $d_i$ ，使得对于每一个 $i$ ，都有 $b_i$ 是 $d_i$ 的倍数。

如果小 W 写出的数，满足 $\prod \limits_{i=1}^{n} {{d_i}^2} \ge \prod \limits_{i=1}^{n} {b_i}$ ，小 S 就会认为小 W 选数的方案是 "资瓷" 的。请问小 W 有多少种选数方案，是被小 S 认为 "资瓷" 的，结果对质数 998244353 取模。两种方案是不一样的，当且仅当存在一个 $b_i$ 或一个 $d_j$ 不同。

输入格式

第一行，一个整数 $n$ ，表示小 S 写下的数字个数。

第二行，由空格隔开的 $n$ 个正整数，表示小 S 写下的数 $a_i$ 。

输出格式

一行，一个整数，表示答案。

样例数据

样例输入

2
2 3

样例输出

5

子任务

• Subtask 1（17pts）：$n \le 5, 1 \le a_i \le 10$。
• Subtask 2（32pts）：存在某个质数 $p$，使得所有 $a_i$ 都是 $p$ 的非负整数次幂。
• Subtask 3（51pts）：没有额外限制。

对于所有数据，都有 $n \le 100,1\le a_i \le 10^9$ 。