QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Hackable ✓
统计

立冬之后,北京的空气就变得稀薄似的,每次呼吸都要十分谨慎,生怕多吸一口空气就会将自己冻伤似的,如此在风中战栗者不一而足。公交车站前,等待 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$ 。