After the beginning of winter, the air in Beijing becomes thin, as if every breath must be taken with great caution for fear of being frostbitten by an extra gulp of air; many people shiver in the wind in this way. In front of the bus stop, people waiting for the 819 bus form a long queue. Perhaps because the weekend is approaching, there seems to be a hint less fatigue on their faces. At this moment, Little W is just looking at the moon in the night sky, watching the bustling crowd pass by, shaking his body to gain a trace of warmth, quietly waiting for the bus to arrive.
While waiting for the bus, Little S writes down $n$ positive integers $a_i$. Little W will first write down $n$ positive integers $b_i$ such that for every $i$, $a_i$ is a multiple of $b_i$. After writing these, Little W will then write down $n$ positive integers $d_i$ such that for every $i$, $b_i$ is a multiple of $d_i$.
If the numbers written by Little W satisfy $\prod \limits_{i=1}^{n} {{d_i}^2} \ge \prod \limits_{i=1}^{n} {b_i}$, Little S considers Little W's selection scheme to be "supported." How many selection schemes of Little W are considered "supported" by Little S? Output the result modulo the prime 998244353. Two schemes are different if and only if there exists at least one $b_i$ or one $d_j$ that is different.
Input
The first line contains an integer $n$, representing the number of integers written by Little S.
The second line contains $n$ positive integers separated by spaces, representing the numbers $a_i$ written by Little S.
Output
A single line containing an integer representing the answer.
Examples
Input 1
2
2 3Output 1
5Subtasks
- Subtask 1 (17 pts): $n \le 5, 1 \le a_i \le 10$.
- Subtask 2 (32 pts): There exists a prime $p$ such that all $a_i$ are non-negative integer powers of $p$.
- Subtask 3 (51 pts): No additional constraints.
For all data, $n \le 100, 1 \le a_i \le 10^9$.