Game of Prime Moves

Two players, Yopilla and yww, play a game on a line of n points numbered 1, 2, …, n. At point i there are a_i indistinguishable pieces. A move consists of choosing a point x that has at least one piece, selecting a positive number y (1 ≤ y ≤ a_x) of pieces from that point, and moving all the chosen pieces to point z = (\frac{x}{p}) for some prime (p) dividing (x) (i.e. (p \mid x)). The moves are only allowed if (x > 1) (since 1 has no prime divisors).

The game proceeds as follows. Yopilla makes the very first move randomly – that is, he selects uniformly at random one of the valid moves (distinguished by the triple ((x,y,z))). After this random first move, both players play optimally. A player who cannot make any move loses.

Assume that each piece at point i is an independent subgame with value (g(i)) defined by the recurrence [ g(1)=0,\quad g(x)=\text{mex}{ g(x/p) : p\text{ is a prime divisor of }x} \text{ for } x\ge2. ]

The overall position’s nim-sum is calculated as (S = \bigoplus_{i=1}^{n} \big( a_i\bmod 2==1 ? g(i) : 0 \big)). Note that when making a move from point (x) to (z=x/p), if one moves an odd number of pieces then the nim-sum changes by (g(x)\oplus g(z)); if one moves an even number of pieces the nim‐sum remains unchanged. Since after Yopilla’s random first move the turn passes to his opponent, the subsequent position is winning for Yopilla if and only if the resulting nim-sum is 0.

Your task is to compute the probability (as a fraction) that Yopilla wins, modulo (998244353). More precisely, let (x, y, z) be a valid move. For each move, if y is odd then the new nim sum is (S \oplus g(x) \oplus g(z)); if y is even then it remains (S). Yopilla wins if after his first move the nim-sum is 0. Since Yopilla’s first move is chosen uniformly at random among all valid moves, you have to calculate the ratio [ \frac{\text{#winning moves}}{\text{#all moves}}, ] modulo (998244353), where the number of winning moves is computed by summing over every point (x) with pieces and every prime divisor (p) of (x):

• If (S = 0), then every move that transfers an even number (i.e. one of (\lfloor a_x/2 \rfloor) choices) results in a winning position.
• If (S \oplus g(x) \oplus g(z) = 0) (with (z=x/p)), then every move moving an odd number (i.e. (\lceil a_x/2 \rceil) choices) results in a winning position.

Output the result as an integer modulo (998244353), where the fraction is computed using the modular inverse.

Note: It is guaranteed that there is at least one valid move (i.e. the total number of moves is positive).

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^5)), the number of points. The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n) ((0 \le a_i \le 10^9)), where (a_i) is the number of pieces at point (i).

outputFormat

Output a single integer, the probability (as a fraction, computed modulo (998244353)) that Yopilla wins the game.

sample

3
0 1 1

0