F. Stone
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Zayin and Ziyin are playing a game with $$$n$$$ piles of stones, where the $$$i$$$-th pile has $$$a_i$$$ stones for each $$$1\le i\le n$$$. Zayin and Ziyin play in turn, with Zayin going first.

  • First, Zayin chooses a positive integer $$$s_1$$$ and some piles with at least $$$s_1$$$ stones, removes $$$s_1$$$ stones from each of the chosen piles.
  • Then Ziyin chooses a positive integer $$$s_2$$$ such that $$$s_2$$$ divides $$$s_1$$$ and some piles with at least $$$s_2$$$ stones, removes $$$s_2$$$ stones from each of the chosen piles.
  • Then Zayin chooses a positive integer $$$s_3$$$ such that $$$s_3$$$ divides $$$s_2$$$ and some piles with at least $$$s_3$$$ stones, removes $$$s_3$$$ stones from each of the chosen piles.
  • ...
  • In general, $$$s_i$$$, the number of stones removed in each of the chosen piles in turn $$$i$$$, must divide $$$s_{i-1}$$$ for $$$i \gt 1$$$.

The one who is unable to remove stones in his turn lose.

Compute the number of strategies Zayin can make in his first turn in order to guarantee a win no matter what choices Ziyin makes.

Two strategies are considered to be different if they remove a different number of stones or they remove stones from different set of piles.

Input

The first line contains the number of stone piles $$$n\ (1\le n\le 10^6)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n\ (1\le a_i\le 10^9)$$$ - the number of stones in each pile.

Output

The only line contains an integer, representing the number of strategies Zayin can make in his first turn modulo $$$998244353$$$.

Example
Input
9
9 9 8 2 4 4 3 5 3
Output
2